Last Updated: 26 Aug, 2020
Successor Problem
Moderate
Asked in companies
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.
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.
Approaches
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:
- First Convert the given integer N into a string ‘S’.
- Traverse from right to left and find the first index at which the digit is smaller than the digit at its right side i.e S[ i ] < S[i + 1]. If the string is non-ascending order then there won’t be any such index so we will return -1. Otherwise, we’ll store the index ‘i’ in a variable ‘indexOfFirstSmallerDigit’.
- Now, we need to find the index at the right side of the ‘indexOfFirstSmallerDigit’ where the digit present is just greater than the digit present at the indexOfFirstSmallerDigit. It can be simply done by traversing from right to left and the first digit which is greater than the digit at firstGreaterIndex will be our required index let’s say it ‘indexTobeSwapped’. It is because the digits at the right side of the indexOfFirstSmallerDigit are present in non-ascending order.
- Swap the digit at the indices indexOfFirstSmallerDigit and indexTobeSwapped. The digits at the right side are still in non-ascending order. To make it non-descending we can sort that but it will increase the time complexity. Therefore simply reverse the digits present at the right side of the indexOfFirstSmallerDigit.
- Convert the string back to the integer and return it.