Chuyển đến nội dung chính

Tìm số nhỏ nhất lớn hơn có cùng số chữ số (C++, Java, Python)

Đề Bài: Cho một số n, tìm số nhỏ nhất có cùng tập hợp chữ số với n và lớn hơn n. Nếu n là số lớn nhất có cùng số chữ số, thì in ra “not possible”.

Ví dụ:

Input:  n = "218765"
Output: "251678"

Input:  n = "1234"
Output: "1243"

Input: n = "4321"
Output: "Not Possible"

Input: n = "534976"
Output: "536479"

Trích: Đề Thi HSG Thành Phố HCM 2008 – 2009

Lời Giải:

Sau đây là thuật toán:

  • Nếu tất cả các chữ số được sắp xếp theo thứ tự giảm dần, thì kết quả luôn là “Not possible”. Ví dụ: 4321.
  • Nếu tất cả các chữ số được sắp xếp theo thứ tự tăng dần, thì chúng ta cần hoán đổi hai chữ số cuối cùng. Ví dụ: 1234.
  • Đối với các trường hợp khác, chúng ta cần xử lý số nhỏ nhất bên phải
// C++ program to find the smallest number which greater than a given number 
// and has same set of digits as given number 
#include <iostream> 
#include <cstring> 
#include <algorithm> 
using namespace std; 

// Utility function to swap two digits 
void swap(char *a, char *b) 
{ 
   char temp = *a; 
   *a = *b; 
   *b = temp; 
} 

// Given a number as a char array number[], this function finds the 
// next greater number. It modifies the same array to store the result 
void findNext(char number[], int n) 
{ 
   int i, j; 

   // I) Start from the right most digit and find the first digit that is 
   // smaller than the digit next to it. 
   for (i = n-1; i > 0; i--) 
      if (number[i] > number[i-1]) 
      break; 

   // If no such digit is found, then all digits are in descending order 
   // means there cannot be a greater number with same set of digits 
   if (i==0) 
   { 
      cout << "Next number is not possible"; 
      return; 
   } 

   // II) Find the smallest digit on right side of (i-1)'th digit that is 
   // greater than number[i-1] 
   int x = number[i-1], smallest = i; 
   for (j = i+1; j < n; j++) 
      if (number[j] > x && number[j] < number[smallest]) 
         smallest = j; 

   // III) Swap the above found smallest digit with number[i-1] 
   swap(&number[smallest], &number[i-1]); 

   // IV) Sort the digits after (i-1) in ascending order 
   sort(number + i, number + n); 

   cout << "Next number with same set of digits is " << number; 

   return; 
} 

// Driver program to test above function 
int main() 
{ 
   char digits[] = "534976"; 
   int n = strlen(digits); 
   findNext(digits, n); 
   return 0; 
} 

 

// Java program to find next greater 
// number with same set of digits. 
import java.util.Arrays; 

public class nextGreater 
{ 
   // Utility function to swap two digit 
   static void swap(char ar[], int i, int j) 
   { 
      char temp = ar[i]; 
      ar[i] = ar[j]; 
      ar[j] = temp; 
   } 

   // Given a number as a char array number[], 
   // this function finds the next greater number. 
   // It modifies the same array to store the result 
   static void findNext(char ar[], int n) 
   { 
      int i; 
      
      // I) Start from the right most digit 
      // and find the first digit that is smaller 
      // than the digit next to it. 
      for (i = n - 1; i > 0; i--) 
      { 
         if (ar[i] > ar[i - 1]) { 
            break; 
         } 
      } 
      
      // If no such digit is found, then all 
      // digits are in descending order means 
      // there cannot be a greater number with 
      // same set of digits 
      if (i == 0) 
      { 
         System.out.println("Not possible"); 
      } 
      else
      { 
         int x = ar[i - 1], min = i; 
         
         // II) Find the smallest digit on right 
         // side of (i-1)'th digit that is greater 
         // than number[i-1] 
         for (int j = i + 1; j < n; j++) 
         { 
            if (ar[j] > x && ar[j] < ar[min]) 
            { 
               min = j; 
            } 
         } 

         // III) Swap the above found smallest 
         // digit with number[i-1] 
         swap(ar, i - 1, min); 

         // IV) Sort the digits after (i-1) 
         // in ascending order 
         Arrays.sort(ar, i, n); 
         System.out.print("Next number with same" + 
                           " set of digits is "); 
         for (i = 0; i < n; i++) 
            System.out.print(ar[i]); 
      } 
   } 

   public static void main(String[] args) 
   { 
      char digits[] = { '5','3','4','9','7','6' }; 
      int n = digits.length; 
      findNext(digits, n); 
   } 
} 
# Python program to find the smallest number which 
# is greater than a given no. has same set of 
# digits as given number 

# Given number as int array, this function finds the 
# greatest number and returns the number as integer 
def findNext(number,n): 
   
   # Start from the right most digit and find the first 
   # digit that is smaller than the digit next to it 
   for i in range(n-1,0,-1): 
      if number[i] > number[i-1]: 
         break
         
   # If no such digit found,then all numbers are in 
   # descending order, no greater number is possible 
   if i == 1 and number[i] <= number[i-1]: 
      print ("Next number not possible") 
      return
      
   # Find the smallest digit on the right side of 
   # (i-1)'th digit that is greater than number[i-1] 
   x = number[i-1] 
   smallest = i 
   for j in range(i+1,n): 
      if number[j] > x and number[j] < number[smallest]: 
         smallest = j 
      
   # Swapping the above found smallest digit with (i-1)'th 
   number[smallest],number[i-1] = number[i-1], number[smallest] 
   
   # X is the final number, in integer datatype 
   x = 0
   # Converting list upto i-1 into number 
   for j in range(i): 
      x = x * 10 + number[j] 
   
   # Sort the digits after i-1 in ascending order 
   number = sorted(number[i:]) 
   # converting the remaining sorted digits into number 
   for j in range(n-i): 
      x = x * 10 + number[j] 
   
   print ("Next number with set of digits is",x) 


# Driver Program to test above function 
digits = "534976"               

# converting into integer array, 
# number becomes [5,3,4,9,7,6] 
number = list(map(int ,digits)) 
findNext(number, len(digits)) 

# This code is contributed by Harshit Agrawal 

 

 

The post Tìm số nhỏ nhất lớn hơn có cùng số chữ số (C++, Java, Python) first appeared on Techacademy.



Nhận xét

Bài đăng phổ biến từ blog này

Hướng Dẫn Cài Đặt Python Trên Máy Tính?

Python là một ngôn ngữ lập trình phổ biến và được sử dụng rộng rãi trong lĩnh vực phát triển phần mềm và khoa học dữ liệu. Để bắt đầu sử dụng Python trên máy tính của bạn, bạn cần cài đặt nó. Trong bài viết này, chúng tôi sẽ hướng dẫn bạn cách cài đặt Python trên máy tính một cách dễ dàng. I. Cài Đặt Python Trên Vscode Python là một ngôn ngữ lập trình phổ biến và VS Code là một trình soạn thảo mã nguồn được ưa chuộng. Kết hợp cả hai, bạn có thể tận dụng lợi ích của cả hai công cụ để phát triển ứng dụng Python một cách hiệu quả. Trong bài viết này, chúng tôi sẽ hướng dẫn cách cài đặt Python trên VS Code. Bước 1: Cài đặt VS Code Trước khi bắt đầu, bạn cần cài đặt VS Code trên máy tính của mình. Truy cập trang web vscode.com, tải xuống phiên bản phù hợp với hệ điều hành của bạn và làm theo hướng dẫn trên màn hình để hoàn tất quá trình cài đặt. Bước 2: Cài đặt Extension Python cho VS Code Sau khi cài đặt VS Code, bạn cần cài đặt extension Python để hỗ trợ phát triển ứng dụng Python t...

Files Trong C++

C++ Files Thư viện fstream cho phép chúng tôi làm việc với các tệp. Để sử dụng thư viện fstream, hãy bao gồm cả tệp tiêu đề <iostream> VÀ <fstream> chuẩn: Example #include <iostream> #include <fstream> Có ba lớp được bao gồm trong thư viện fstream, được sử dụng để tạo, ghi hoặc đọc tệp: Lớp Sự mô tả ofstream Tạo và ghi vào tệp ifstream Đọc từ tệp fstream Sự kết hợp giữa ofstream và ifstream: tạo, đọc và ghi vào tệp Tạo Và Ghi Vào Tệp Để tạo tệp, hãy sử dụng lớp ofstream hoặc fstream và chỉ định tên của tệp. Để ghi vào tệp, hãy sử dụng toán tử chèn (<<). Example #include <iostream> #include <fstream> using namespace std; int main() { // Create and open a text file ofstream MyFile("filename.txt"); // Write to the file MyFile << "Files can be tricky, but it is fun enough!"; // Close the file MyFile.close(); } Đọc Tệp Để đọc từ một tệp, hãy sử dụng lớp ifstream hoặc fstream và...

Học Lập Trình Android Ở Đâu TpHCM, Hà Nội, Đà Nẵng ? Tốt Nhất, Uy Tín Nhất

Học lập trình Android là một trong những khóa học lập trình được nhiều bạn trẻ tìm kiếm nhất hiện nay bởi mực lương hấp dẫn và ổn định của một lập trình viên android. Đối với các bạn trẻ bắt đầu theo học android việc suy nghĩ học lập trình android ở đâu luôn là vấn đề được rất nhiều quan tâm. Để biết được câu trả lời khách quan nhất về học lập trình android ở đâu tại TpHCM, Hà Nội, Đà Nẵng? Mời bạn tham khảo ngay ý kiến từ Techacademy đưa ra dưới đây nhé! I. Học lập trình android ở đâu tốt nhất Hà Nôi, TpHCM, Đà Nẵng Dưới đây là danh sách các trung tâm đào tạo lập trình android hàng đầu Việt Nam hiện nay. 1, Techacademy Sử dụng phương pháp giảng dạy lập trình android được hiệu quả, giúp học viện hiểu bài và áp dụng thục hành ngay trong thực tế. Đây là phương pháp dạy lập trình android hiệu quả nhất hiện nay, giúp học viên xây dựng sự tự tin khi thực hành. Techacademy là trung tâm đào tạo lập trình android hàng đầu tại Việt Nam, được thành lập với đội ngũ giảng viên, chuyên gia lậ...