Next Greater Number

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
25 upvotes
Asked in companies
Morgan StanleySamsungArcesium

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
1234
Sample Output 1:
1243
Explanation For Sample Input 1:
1243 is the next greater number consisting of the same set of digits (1,2,3 and 4)
Sample Input 2:
2
4321
65312
Sample Output 2:
-1
65321
Hint

Try greedy.

Approaches (1)
Greedy Implementation
  • 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.
Time Complexity

O(N), where N is the length of the given string.

 

Since, we are traversing through the length of the string only once.

Space Complexity

O(1), 

 

Since we are using constant extra space.

Code Solution
(100% EXP penalty)
Next Greater Number
Full screen
Console