Tuesday, January 27, 2015

Next greater number with same digits

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 do 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.

Even after swapping, the value can be minimized further. 

For example 57862, we don't  swap 8,2 or 8,6 as they are in descending order. 
We swap the 7,8; the value becomes 58762. If we order the digits after 8 in ascending order, it becomes 58267 which is the required answer.

Here is the C++ implementation of the above. For python code click this link.