Given a number
N, find the smallest number that has same set-of-digits as
Nand is greater than
Nis the greatest possible number with its set-of-digits, then print the same number
Input : "12345" Output : "12354"
Input : "54321" Output : "54321" Explanation : No number is greater than 54321 with same set of digits, thats why print same number.
Input : "12321" Output : "13122"
If the digits are all sorted in strictly descending order, then the number itself would be our answer as there is no bigger number than that.
If the digits are all sorted in strictly increasing order, then just swap the last two digits. For example,
12345will change to
For all other cases, we need to process all the digits in the number from right to left as we need to find the smallest of the greater numbers.
Start traversing the given number from rightmost digit till you reach a digit that is just smaller than its right digit, say index of this digit be
125321, here if we scan from right to left,
2is the first digit that is less than
2is our ithindex digit.
Now again traverse to the right of this index
iand find the smallest digit that is just greater than the digit at ith index. Let’s say the found index is
jat the right of
i. Now if we traverse right of
2, the smallest digit that is greater than
Swap digits at ith and jth index. After swapping
Sort digits from
(i+1)to the rightmost index in increasing order. After sorting,
131225, which is our required solution.
A few optimizations can be made in this approach and significantly improve the Time Complexity of the approach according to the data structures and algorithms in c++.
Linear Searchused in
Step-2can be replaced with
Binary Searchas the right digits are already sorted. This reduces
Step-4can be done in
O(nlogn)as only one digit needs to be repositioned else all are already sorted.
Optimizationwould improve our solution from
O(n+logn+n)giving overall time complexity of
n = number-of-digits-of-a-given-number.