Next Greater Number
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

Question

Next Greater Number

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

Accepted Answer

Observations:
1. If all digits are sorted in descending order, then output is always “Not Possible”.
2. If all digits are sorted in ascending order, then we need to swap last two digits.
3. For other cases, we need to process the number from rightmost side to find the smallest of all greater numbers.

Steps:
1. Traverse the given number from rightmost digit, keep traversing till you find a digit which is smaller than the previously traversed digit. If no such digit is found, then output is “Not Possible”.
2. Now search the right side of above found digit ‘d’ for the smallest digit greater than ‘d’.
3. Swap the above found two digits.
4. Now sort all digits from position next to ‘d’ to the end of number. The number that we get after sorting is the required output.

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1),

Since we are using constant extra space.

Time Complexity: O(n)Explanation:

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

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

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:

Note:

Input Format:

Output Format:

Note:

Constraints:

Top MakeMyTrip Senior QA Engineer interview questions & answers

Popular interview questions of Senior QA Engineer

Top HR questions asked in MakeMyTrip Senior QA Engineer