Next Number with distinct digits
Given an integer N, the task is to find the next number with distinct digits in it.
Examples:
Input: N = 20
Output: 21
The next integer with all distinct digits after 20 is 21.Input: N = 2019
Output: 2031
Approach:
- Count the total number of digits in the number N using the approach discussed in this article.
- Count the total number of distinct digits in N.
- If the count of a total number of digits and the number of distinct digits in N is equal, then return the number, otherwise, increment the number by one and repeat the previous steps.
Below is the implementation of the above approach:
C++
// C++ program to find next consecutive // Number with all distinct digits #include <bits/stdc++.h> using namespace std; // Function to count distinct // digits in a number int countDistinct( int n) { // To count the occurrence of digits // in number from 0 to 9 int arr[10] = { 0 }; int count = 0; // Iterate over the digits of the number // Flag those digits as found in the array while (n) { int r = n % 10; arr[r] = 1; n /= 10; } // Traverse the array arr and count the // distinct digits in the array for ( int i = 0; i < 10; i++) { if (arr[i]) count++; } return count; } // Function to return the total number // of digits in the number int countDigit( int n) { int c = 0; // Iterate over the digits of the number while (n) { int r = n % 10; c++; n /= 10; } return c; } // Function to return the next // number with distinct digits int nextNumberDistinctDigit( int n) { while (n < INT_MAX) { // Count the distinct digits in N + 1 int distinct_digits = countDistinct(n + 1); // Count the total number of digits in N + 1 int total_digits = countDigit(n + 1); if (distinct_digits == total_digits) { // Return the next consecutive number return n + 1; } else // Increment Number by 1 n++; } return -1; } // Driver code int main() { int n = 2019; cout << nextNumberDistinctDigit(n); return 0; } |
Java
// Java program to find next consecutive // Number with all distinct digits import java.io.*; public class GFG { final static int INT_MAX = Integer.MAX_VALUE ; // Function to count distinct // digits in a number static int countDistinct( int n) { // To count the occurrence of digits // in number from 0 to 9 int arr[] = new int [ 10 ]; int count = 0 ; // Iterate over the digits of the number // Flag those digits as found in the array while (n != 0 ) { int r = n % 10 ; arr[r] = 1 ; n /= 10 ; } // Traverse the array arr and count the // distinct digits in the array for ( int i = 0 ; i < 10 ; i++) { if (arr[i] != 0 ) count++; } return count; } // Function to return the total number // of digits in the number static int countDigit( int n) { int c = 0 ; // Iterate over the digits of the number while (n != 0 ) { int r = n % 10 ; c++; n /= 10 ; } return c; } // Function to return the next // number with distinct digits static int nextNumberDistinctDigit( int n) { while (n < INT_MAX) { // Count the distinct digits in N + 1 int distinct_digits = countDistinct(n + 1 ); // Count the total number of digits in N + 1 int total_digits = countDigit(n + 1 ); if (distinct_digits == total_digits) { // Return the next consecutive number return n + 1 ; } else // Increment Number by 1 n++; } return - 1 ; } // Driver code public static void main (String[] args) { int n = 2019 ; System.out.println(nextNumberDistinctDigit(n)); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 program to find next consecutive # Number with all distinct digits import sys INT_MAX = sys.maxsize; # Function to count distinct # digits in a number def countDistinct(n): # To count the occurrence of digits # in number from 0 to 9 arr = [ 0 ] * 10 ; count = 0 ; # Iterate over the digits of the number # Flag those digits as found in the array while (n ! = 0 ): r = int (n % 10 ); arr[r] = 1 ; n / / = 10 ; # Traverse the array arr and count the # distinct digits in the array for i in range ( 10 ): if (arr[i] ! = 0 ): count + = 1 ; return count; # Function to return the total number # of digits in the number def countDigit(n): c = 0 ; # Iterate over the digits of the number while (n ! = 0 ): r = n % 10 ; c + = 1 ; n / / = 10 ; return c; # Function to return the next # number with distinct digits def nextNumberDistinctDigit(n): while (n < INT_MAX): # Count the distinct digits in N + 1 distinct_digits = countDistinct(n + 1 ); # Count the total number of digits in N + 1 total_digits = countDigit(n + 1 ); if (distinct_digits = = total_digits): # Return the next consecutive number return n + 1 ; else : # Increment Number by 1 n + = 1 ; return - 1 ; # Driver code if __name__ = = '__main__' : n = 2019 ; print (nextNumberDistinctDigit(n)); # This code is contributed by PrinciRaj1992 |
C#
// C# program to find next consecutive // Number with all distinct digits using System; class GFG { readonly static int INT_MAX = int .MaxValue ; // Function to count distinct // digits in a number static int countDistinct( int n) { // To count the occurrence of digits // in number from 0 to 9 int []arr = new int [10]; int count = 0; // Iterate over the digits of the number // Flag those digits as found in the array while (n != 0) { int r = n % 10; arr[r] = 1; n /= 10; } // Traverse the array arr and count the // distinct digits in the array for ( int i = 0; i < 10; i++) { if (arr[i] != 0) count++; } return count; } // Function to return the total number // of digits in the number static int countDigit( int n) { int c = 0; // Iterate over the digits of the number while (n != 0) { int r = n % 10; c++; n /= 10; } return c; } // Function to return the next // number with distinct digits static int nextNumberDistinctDigit( int n) { while (n < INT_MAX) { // Count the distinct digits in N + 1 int distinct_digits = countDistinct(n + 1); // Count the total number of digits in N + 1 int total_digits = countDigit(n + 1); if (distinct_digits == total_digits) { // Return the next consecutive number return n + 1; } else // Increment Number by 1 n++; } return -1; } // Driver code public static void Main(String[] args) { int n = 2019; Console.WriteLine(nextNumberDistinctDigit(n)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript program to find next consecutive // Number with all distinct digits let INT_MAX = Number.MAX_VALUE; // Function to count distinct // digits in a number function countDistinct(n) { // To count the occurrence of digits // in number from 0 to 9 let arr = new Array(10); arr.fill(0); let count = 0; // Iterate over the digits of the number // Flag those digits as found in the array while (n != 0) { let r = n % 10; arr[r] = 1; n = parseInt(n / 10, 10); } // Traverse the array arr and count the // distinct digits in the array for (let i = 0; i < 10; i++) { if (arr[i] != 0) count++; } return count; } // Function to return the total number // of digits in the number function countDigit(n) { let c = 0; // Iterate over the digits of the number while (n != 0) { let r = n % 10; c++; n = parseInt(n / 10, 10); } return c; } // Function to return the next // number with distinct digits function nextNumberDistinctDigit(n) { while (n < INT_MAX) { // Count the distinct digits in N + 1 let distinct_digits = countDistinct(n + 1); // Count the total number of digits in N + 1 let total_digits = countDigit(n + 1); if (distinct_digits == total_digits) { // Return the next consecutive number return n + 1; } else // Increment Number by 1 n++; } return -1; } let n = 2019; document.write(nextNumberDistinctDigit(n)); </script> |
2031
Time Complexity: O(logn)
Auxiliary Space: O(1)
Another Approach:
Instead of calculating the number of digits each time, we can use set STL in order to check if a number has only unique digits.
Then we can compare the size of string s formed from a given number and the newly created set.
For example, let us consider the number 1987, then we can convert the number into a string,
C++
int n; cin>>n; string s = to_string(n); |
After that, initialize a set with the contents of string s.
C++
set< int > uniDigits(s.begin(), s.end()); |
Then we can compare the size of string s and the newly created set uniDigits.
Here is the total code
C++
// CPP program for the above program #include <bits/stdc++.h> using namespace std; // Function to find next number // with digit distinct void nextNumberDistinctDigit( int n) { // Iterate from n + 1 to inf for ( int i = n + 1;; i++) { // Convert the no. to // string string s = to_string(i); // Convert string to set using stl set< int > uniDigits(s.begin(), s.end()); // Output if condition satisfies if (s.size() == uniDigits.size()) { cout << i; break ; } } } // Driver Code int main() { int n = 2019; // input the no. // Function Call nextNumberDistinctDigit(n); return 0; } |
Java
// Java Equivalent of the above code import java.util.*; public class Main { public static void main(String[] args) { int n = 2019 ; // Input the no. nextNumberDistinctDigit(n); } // Function to find next number // with digit distinct public static void nextNumberDistinctDigit( int n) { // Iterate from n + 1 to inf for ( int i = n + 1 ;; i++) { // Convert the no. to // string String s = Integer.toString(i); // Convert string to set using stl Set<Integer> uniDigits = new HashSet<>(); for ( int j = 0 ; j < s.length(); j++) { uniDigits.add(Character.getNumericValue(s.charAt(j))); } // Output if condition satisfies if (s.length() == uniDigits.size()) { System.out.println(i); break ; } } } } |
Python3
# Python program for the above program # Function to find next number # with digit distinct import sys def nextNumberDistinctDigit(n): # Iterate from n + 1 to inf for i in range (n + 1 ,sys.maxsize): # Convert the no. to # string s = str (i) # Convert string to set using stl uniDigits = set ([char for char in s]) # Output if condition satisfies if ( len (s) = = len (uniDigits)): print (i) break # Driver Code n = 2019 # input the no. # Function Call nextNumberDistinctDigit(n) # This code is contributed by shinjanpatra |
C#
// C# Equivalent of the above code using System; using System.Collections.Generic; namespace NextNumberDistinctDigit { class Program { static void Main( string [] args) { int n = 2019; // Input the no. NextNumberDistinctDigit(n); } // Function to find next number // with digit distinct public static void NextNumberDistinctDigit( int n) { // Iterate from n + 1 to inf for ( int i = n + 1;; i++) { // Convert the no. to // string string s = i.ToString(); // Convert string to set using stl HashSet< int > uniDigits = new HashSet< int >(); for ( int j = 0; j < s.Length; j++) { uniDigits.Add( int .Parse(s[j].ToString())); } // Output if condition satisfies if (s.Length == uniDigits.Count) { Console.WriteLine(i); break ; } } } } } |
Javascript
<script> // JavaScript program for the above program // Function to find next number // with digit distinct function nextNumberDistinctDigit(n) { // Iterate from n + 1 to inf for (let i = n + 1;; i++) { // Convert the no. to // string let s = i.toString(); // Convert string to set using stl let uniDigits = new Set(s.split( '' )); // Output if condition satisfies if (s.length == uniDigits.size) { document.write(i); break ; } } } // Driver Code let n = 2019; // input the no. // Function Call nextNumberDistinctDigit(n); // This code is contributed by shinjanpatra </script> |
2031
Contact Us