Find Next number having distinct digits from the given number N
Given a natural number N, the task is to find the next number having distinct digits from the given number.
Examples:
Input: N = 19
Output: 20
Explanation:
Next number to 19 whose digits are different from 19 is 20.
Input: N = 2019
Output: 3333
Explanation:
Next number to 2019 whose digits are different from 2019 is 3333.
Approach: The idea is to use hashing to compute the next number with distinct digit from the given number –
- Create a hash array to store the digits present in the number, store the most significant digit and also store the number of digits present in the number in a count variable
- Find the next digit for the most significant bit which is not present in the number and greater than the current most significant digit.
- If the next most significant digit is not found then increase the number of digits by incrementing the count and find the most significant digit between 1 to 9 which is not present in the number.
- If the next most significant digit is found then find the minimum digit next which is not present in the number between 0 to 9.
- Iterate over the number of digits from 1 to count
- Multiply the most significant digit by 10 and add the next digit which is not present in the given number.
Below is the implementation of the above approach:
C++
// C++ implementation to find // the next distinct digits number #include <bits/stdc++.h> using namespace std; // Function to find the // next distinct digits number void findNextNumber( int n) { int h[10] = { 0 }; int i = 0, msb = n, rem = 0; int next_num = -1, count = 0; // Loop to find the distinct // digits using hash array // and the number of digits while (msb > 9) { rem = msb % 10; h[rem] = 1; msb /= 10; count++; } h[msb] = 1; count++; // Loop to find the most significant // distinct digit of the next number for (i = msb + 1; i < 10; i++) { if (h[i] == 0) { next_num = i; break ; } } // Condition to check if the number // is possible with the same number // of digits count if (next_num == -1){ for (i = 1; i < msb; i++){ if (h[i] == 0){ next_num = i; count++; break ; } } } // Condition to check if the desired // most significant distinct // digit is found if (next_num > 0){ // Loop to find the minimum next digit // which is not present in the number for (i = 0; i < 10; i++) { if (h[i] == 0) { msb = i; break ; } } // Computation of the number for (i = 1; i < count; i++) { next_num = ((next_num * 10) + msb); } // Condition to check if the number is // greater than the given number if (next_num > n) cout << next_num << "\n" ; else cout << "Not Possible \n" ; } else { cout << "Not Possible \n" ; } } // Driver Code int main() { int n = 2019; findNextNumber(n); return 0; } |
C
// C implementation to find //next distinct digits number #include <stdio.h> // Function to find the // next distinct digits number void findNextNumber( int n) { int h[10] = { 0 }; int i = 0, msb = n, rem = 0; int next_num = -1, count = 0; // Loop to find the distinct // digits using hash array // and the number of digits while (msb > 9) { rem = msb % 10; h[rem] = 1; msb /= 10; count++; } h[msb] = 1; count++; // Loop to find the most significant // distinct digit of the next number for (i = msb + 1; i < 10; i++) { if (h[i] == 0) { next_num = i; break ; } } // Condition to check if the number // is possible with the same number // of digits count if (next_num == -1){ for (i = 1; i < msb; i++){ if (h[i] == 0){ next_num = i; count++; break ; } } } // Condition to check if the desired // most significant distinct // digit is found if (next_num > 0){ // Loop to find the minimum next digit // which is not present in the number for (i = 0; i < 10; i++) { if (h[i] == 0) { msb = i; break ; } } // Computation of the number for (i = 1; i < count; i++) { next_num = ((next_num * 10) + msb); } // Condition to check if the number is // greater than the given number if (next_num > n) printf ( "%d\n" , next_num); else printf ( "\nNot Possible" ); } else { printf ( "Not Possible \n" ); } } // Driver Code int main() { int n = 2019; findNextNumber(n); return 0; } // This code is contributed by allwink45 |
Java
// Java implementation to find // the next distinct digits number class GFG{ // Function to find the // next distinct digits number static void findNextNumber( int n) { int h[] = new int [ 10 ]; int i = 0 , msb = n, rem = 0 ; int next_num = - 1 , count = 0 ; // Loop to find the distinct // digits using hash array // and the number of digits while (msb > 9 ) { rem = msb % 10 ; h[rem] = 1 ; msb /= 10 ; count++; } h[msb] = 1 ; count++; // Loop to find the most significant // distinct digit of the next number for (i = msb + 1 ; i < 10 ; i++) { if (h[i] == 0 ) { next_num = i; break ; } } // Condition to check if the number // is possible with the same number // of digits count if (next_num == - 1 ){ for (i = 1 ; i < msb; i++){ if (h[i] == 0 ){ next_num = i; count++; break ; } } } // Condition to check if the desired // most significant distinct // digit is found if (next_num > 0 ){ // Loop to find the minimum next digit // which is not present in the number for (i = 0 ; i < 10 ; i++) { if (h[i] == 0 ) { msb = i; break ; } } // Computation of the number for (i = 1 ; i < count; i++) { next_num = ((next_num * 10 ) + msb); } // Condition to check if the number is // greater than the given number if (next_num > n) System.out.print(next_num+ "\n" ); else System.out.print( "Not Possible \n" ); } else { System.out.print( "Not Possible \n" ); } } // Driver Code public static void main(String[] args) { int n = 2019 ; findNextNumber(n); } } // This code is contributed by 29AjayKumar |
C#
// C# implementation to find // the next distinct digits number using System; class GFG{ // Function to find the // next distinct digits number static void findNextNumber( int n) { int []h = new int [10]; int i = 0, msb = n, rem = 0; int next_num = -1, count = 0; // Loop to find the distinct // digits using hash array // and the number of digits while (msb > 9) { rem = msb % 10; h[rem] = 1; msb /= 10; count++; } h[msb] = 1; count++; // Loop to find the most significant // distinct digit of the next number for (i = msb + 1; i < 10; i++) { if (h[i] == 0) { next_num = i; break ; } } // Condition to check if the number // is possible with the same number // of digits count if (next_num == -1){ for (i = 1; i < msb; i++){ if (h[i] == 0){ next_num = i; count++; break ; } } } // Condition to check if the desired // most significant distinct // digit is found if (next_num > 0){ // Loop to find the minimum next digit // which is not present in the number for (i = 0; i < 10; i++) { if (h[i] == 0) { msb = i; break ; } } // Computation of the number for (i = 1; i < count; i++) { next_num = ((next_num * 10) + msb); } // Condition to check if the number is // greater than the given number if (next_num > n) Console.WriteLine(next_num); else Console.WriteLine( "Not Possible" ); } else { Console.WriteLine( "Not Possible" ); } } // Driver Code public static void Main( string [] args) { int n = 2019; findNextNumber(n); } } // This code is contributed by Yash_R |
Python 3
# Python 3 implementation to find # the next distinct digits number # Function to find the # next distinct digits number def findNextNumber(n): h = [ 0 for i in range ( 10 )] i = 0 msb = n rem = 0 next_num = - 1 count = 0 # Loop to find the distinct # digits using hash array # and the number of digits while (msb > 9 ): rem = msb % 10 h[rem] = 1 msb / / = 10 count + = 1 h[msb] = 1 count + = 1 # Loop to find the most significant # distinct digit of the next number for i in range (msb + 1 , 10 , 1 ): if (h[i] = = 0 ): next_num = i break # Condition to check if the number # is possible with the same number # of digits count if (next_num = = - 1 ): for i in range ( 1 ,msb, 1 ): if (h[i] = = 0 ): next_num = i count + = 1 break # Condition to check if the desired # most significant distinct # digit is found if (next_num > 0 ): # Loop to find the minimum next digit # which is not present in the number for i in range ( 0 , 10 , 1 ): if (h[i] = = 0 ): msb = i break # Computation of the number for i in range ( 1 ,count, 1 ): next_num = ((next_num * 10 ) + msb) # Condition to check if the number is # greater than the given number if (next_num > n): print (next_num) else : print ( "Not Possible" ) else : print ( "Not Possible" ) # Driver Code if __name__ = = '__main__' : n = 2019 findNextNumber(n) # This code is contributed by Surendra_Gangwar |
Javascript
<script> // Javascript implementation to find // the next distinct digits number // Function to find the // next distinct digits number function findNextNumber(n) { let h = Array.from({length: 10}, (_, i) => 0); let i = 0, msb = n, rem = 0; let next_num = -1, count = 0; // Loop to find the distinct // digits using hash array // and the number of digits while (msb > 9) { rem = msb % 10; h[rem] = 1; msb = Math.floor(msb / 10); count++; } h[msb] = 1; count++; // Loop to find the most significant // distinct digit of the next number for (i = msb + 1; i < 10; i++) { if (h[i] == 0) { next_num = i; break ; } } // Condition to check if the number // is possible with the same number // of digits count if (next_num == -1){ for (i = 1; i < msb; i++){ if (h[i] == 0){ next_num = i; count++; break ; } } } // Condition to check if the desired // most significant distinct // digit is found if (next_num > 0){ // Loop to find the minimum next digit // which is not present in the number for (i = 0; i < 10; i++) { if (h[i] == 0) { msb = i; break ; } } // Computation of the number for (i = 1; i < count; i++) { next_num = ((next_num * 10) + msb); } // Condition to check if the number is // greater than the given number if (next_num > n) document.write(next_num+ "\n" ); else document.write( "Not Possible \n" ); } else { document.write( "Not Possible \n" ); } } // Driver code let n = 2019; findNextNumber(n); </script> |
Output:
3333
Time Complexity: O(logN)
Auxiliary Space: O(logN)
Contact Us