Next Greater Number

Posted: 14 Dec, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given a string S which represents a number. You have to find the smallest number strictly greater than the given number which contains the same set of digits as of the original number i.e the frequency of each digit from 0 to 9 should be exactly the same as in the original number.

For example:
If the given string is 56789, then the next greater number is 56798. Note that although 56790 is also greater than the given number it contains 1 '0' which is not in the original number and also it does not contain the digit '8'.

Note:

The given string is non-empty.

If the answer does not exist, then return -1.

The given number does not contain any leading zeros.
Input Format:
The first line of the input contains an integer T denoting the number of test cases.

The first and the only line of each test case contains a string S representing the number.
Output Format:
The only line of output of each test case should print the number which is just greater than the given number as described above
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= len(S) <= 10^4
Time Limit: 1 sec
Approach 1
  • First of all, we shall consider some base cases before moving on to the actual solution.
    • If all the digits are sorted in ascending order, then just swap the last two digits, and return them, since it will give us the next greater number.
    • If all the digits are sorted in descending order, then return -1, since we will not have any greater number than the given number which may contain the same set of digits
  • This problem is an implementation-based problem, so we shall try to develop the solution step by step.
    • The first thing to note is that we need to start traversing the string from the back since we need the smallest number greater than the given number.
    • Let idx = -1 store the position which is to be swapped.
    • Keep on traversing, until we find a digit, which is smaller than the previous digit. We do so because if we swap these positions, then we will get just a greater number and this index in “idx”.
      • For example, if the number be 984976. We stop at 4 because 4 is smaller than its previous digit which is 9.
    • If we reach the 0th index, then the answer will not exist and hence return -1.
    • Now we search for the next greater digit than just found digit, which is 4 in our example. Swap these 2 positions. So S becomes 986974.
    • Since we have to get the just next greater number, we can reverse the elements from "idx + 1" to the end. So the final answer is 986479.
  • Return the string.
Try Problem