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.