Successor Problem

Moderate

0/80

Average time to solve is 32m

Contributed by

12 upvotes

Problem statement

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

Detailed explanation ( Input/output format, Notes, Images )

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 a single line containing a single integer denoting 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.

The output for each 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.

Sample Input 1:

1
112

Sample Output 1:

Explanation of the Sample Input 1:

From  112 we can have permutations 112, 121, and 211.
The number which precedes 112 is 121.

Sample Input 2 :

2
402356
321

Sample Output 2 :

402365
-1

Console