Successor Problem

Posted: 26 Aug, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Coding Ninjas has given you an integer N. You have to print the number succeeded by the given number in the lexicographically sorted permutation of all digits of the given number.

If the number is the last element of lexicographically sorted permutation of all digits of the given number, then print -1.

For Example:

The lexicographically sorted list of permutation of all digits of the number ‘123’ is:
123
132
213
231
312
321.

If we are given N as 123 then the permutation which precedes 123 is 132.
Similarly, if N is 132 then the permutation which precedes 132 is 213.
For 321 there does not exist any permutation greater than 321. So we need to print -1.
Input Format:
The first line contains an integer 't' which denotes the number of test cases/queries to be run. Then the test cases follow. 

The first and the only line of input for each test case contains an integer 'N'.
Output Format:
For each test case, print the number preceded by the given number in the lexicographically sorted permutation of all digits of the given number and if it does not exist, print -1.

Output for every test case will be printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= t <= 10^5
0 <= N <= 10^17

Time Limit: 1 sec
Approach 1
  • First, check if the number is in non-ascending order then print -1 otherwise follow the below approach.
  • Count the number of times each digit occurs in N and store it. We can use an array of size 10 and initialize all indices from 0 to 9 with value 0.
  • Now run a loop from i = N+1 and count the number of times each digit occurs in i. If this count array and count array of N are the same, then i will be our required next greater permutation.
Try Problem