Problem

Submissions

Hints & solutions

Discuss

Successor Problem

Moderate

0/80

Average time to solve is 32m

Contributed by

12 upvotes

Asked in companies

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

Hint 1

Try to observe the pattern, how the next greater permutation is generated from the given number.

Approaches (1)

Approach 1

Optimal approach

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.

Time Complexity

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

Space Complexity

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.

(100% EXP penalty)

Successor Problem

TUSHAR DEB

Interview problems

Optimal Approach : 100% Perfect Solution

/*
    Time Complexity : O(K)
    Space Complexity :  O(K)

    where 'K' is the number of digits in the integer 'N'.
*/

long long findSuccessor(long long n)
{
    string s = to_string(n);
    int indexOfFirstSmallerDigit = -1;
    int indexTobeSwapped = -1;

    for (int i = s.size() - 2; i >= 0; i--)
    {
        if (s[i] < s[i + 1])
        {
            indexOfFirstSmallerDigit = i;
            break;
        }
    }

    // It means S is in non ascending order so return -1.
    if (indexOfFirstSmallerDigit == -1)
    {
        return -1;
    }

    //Find the index where the digit is just greater than the digit at indexOfFirstSmallerDigit.
    for (int i = s.size() - 1; i > indexOfFirstSmallerDigit; i--)
    {
        if (s[i] > s[indexOfFirstSmallerDigit])
        {
            indexTobeSwapped = i;
            break;
        }
    }

    swap(s[indexOfFirstSmallerDigit], s[indexTobeSwapped]);

    // Reverse the digits at right side of indexOfFirstSmallerDigit.
    int i = indexOfFirstSmallerDigit + 1, j = s.size() - 1;
    while (i < j)
    {
        swap(s[i], s[j]);
        i++;
        j--;
    }

    long long ans = stoll(s);

    return ans;
}

35 views

0 replies

0 upvotes

Codestudio

Interview problems

Discussion thread on Interview Problem | Successor Problem

Hey everyone, creating this thread to discuss the interview problem - Successor Problem.

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Successor Problem

175 views

0 replies

0 upvotes

Console