Problem of the day
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.
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.
1 <= T <= 10 ^ 5
0 <= N <= 10 ^ 17
Time Limit: 1 sec.
1
112
121
From 112 we can have permutations 112, 121, and 211.
The number which precedes 112 is 121.
2
402356
321
402365
-1
Try to observe the pattern, how the next greater permutation is generated from the given number.
If a number has all the digits in non-ascending order for eg ‘332211’ then its next greater permutation does not exist so we can print -1.
Let’s take an example first to understand how the next greater permutation is generated. Let’s say we have N = 872651, the last 1 digit is 1 which is maximum using the digit 1. Last 2 digits are 51 which is maximum using the digits 1 and 5. Last 3 digits are 651 and we can not have any greater permutation by using the digits 6,5 and 1. So let’s take the last 4 digits i.e 2651 Now our problem is to find the next greater permutation of these 4 digits and replacing it with the last 4 digits of the original number which will be our answer. Now 2 should be replaced by a digit greater than it and to have just the next greater number, that digit should be as far to the right as possible. 5 satisfies this criterion so we’ll replace 2 with 5. Now to have the minimum number starting with 5 all the remaining digits should be in non-descending order. Therefore we have 5126. Our final answer will be 875126 which is the permutation preceding N.
Therefore Algorithm is:
O(K), where ‘K’ is the number of digits in the integer ‘N’.
To find ‘indexOfFirstSmallerDigit’ and ‘indexTobeSwapped’ two traversals are required so time complexity is O(K + K) and to sort the part at the right side of ‘indexOfFirstSmallerDigit’ we are simply reversing it so again O(K).
O(K), where ‘K’ is the number of digits in the integer ‘N’.
Because we are converting ‘N’ to a string and storing all digits.