Given a number, how do we find the next greater number with the same digits?
For example if the given number is 123, the next greater number with the same digits is 132.
Similarly for 23876, the output is 26378.
If all the digits of the number are in decreasing order (Eg. 54321), there is no greater number with the same digits.
Let us look at the solution approach. If we simply sort the digits of the number in descending order, we will surely get the greater number with the same digits.
For example if we sort the digits of 123, we get 321.
But we are looking for the least among all greater numbers. In the above example 132 is least among {132, 213, 231, 312, 321}. How to form such a number?
If we swap any two digits a number, it’s value either increases or decreases depends on their order.
For example consider 58762.
- If we swap 8,7 the value (57862) decreases because the bigger digit appears before smaller digit.
- If we swap 5,6 the value (68752) increases because the lesser digit appears before the bigger digit.
So we have to find a pair of digits such that the lesser digit appears before the bigger digit.
We know that as we move from right to left digits in a number, the place value of them increases. So to keep the value as low as possible, we need to find such a pair from right to left.
After finding such a number, we need to swap this with least number greater than it and appearing to the right of it.
For example consider the number 6276530
Scanning from right to left 2 is the first number smaller than it’s right.
3 is the least number greater than 2 and appearing to the right of it.
Swapping 2 and 3, we get 6376520
Even after swapping, the value can be minimized further.
We have to order all the digits after 3 in ascending order, whih results in 6302567
Here is the C++ implementation of the above. For python code click this link.