Find the next greater number using same digits

Given a number, find the next greater number using same digits(or by rearranging the digits). For example, if the given number is 1234 then next greater number would be 1243. For the input 1243, next greater number would be 1324. If the input is 6938652 then the output should be the number 6952368.

If there is no next greater number possible, then the program should return the same number. For example, for number 4321, same number 4321 would be returned.


Video coming soon!



Subscribe for more updates


Algorithm/Insights

We think that the algorithm to solve this problem is best understood using examples. Say we want to get the next higher number for number 1234. If we swap last two digits, we have number 1243 which is next higher number of 1234. Now the next higher number for number 1243 would be 1324. If you observe carefully for input 1243, what we have done is swapped digits 2 and 3 which gets us number - 1342 and then sorted digits after digit 3(42).

Looking at an another example, if the given number is 6938652 then output would be 6952368. Here we have used two steps -
1. Swap digit 3 and 5 which gives us number 6958632.
2. Sort digits after the digit 5(8632) which gets us to number 6952368.

Now let us see how we can find out the digits to be swapped in the first step above. We start processing the given number digit by digit from the last digit of the number. In this case(6938652), we start processing from digit 2. We keep looking for the first digit which breaks the sorted ordering of digits. Now observe that the next digit of digit 2 is 5 which is greater than 2 and hence maintains the sorted ordering. Next digit of 5 is 6 which also maintains sorted ordering. Next digit 8 also does not violate sorted ordering. When we look at next digit 3, because it it less than the previously seen digit(8), it is the first digit to break the sorted ordering. Now we find out the next higher digit of digit 3 in the right portion of digit 3 in the number. Next higher digit of digit 3 in portion 8652 is digit 5. Now we swap these two digits which we have found - first digit which breaks the sorted ordering and second digit which is next higher digit in the right portion of first found digit. Once this swap operation is complete we get the intermediate number as 6958632. Now we need to sort the right portion of the index which we found while searching for digit breaking the sorted ordering. We found the digit 3 at index 2, and hence we need to sort right portion of this intermediate number 6958632 starting at index 3 - that portion would be number 8632. After sorting this we get the output as 6952368. As you can confirm, the portion that needs to be sorted would always be in reverse sorted order and therefore reversing this portion would get it in sorted order.

Hopefully, above example has helped to understand the algorithm and its intuition. Now let's look at the formal steps of the algorithm -
1. Starting from last digit of given number, find the first digit which breaks the sorted ordering. Let the index of this found digit be 'i' and the digit be number[i].
2. Find the next greater digit in the right portion of number[i] - that is from digit at index i+1 to last digit. Let that digit be number[j] at index 'j'.
3. Swap digits at index 'i' and 'j'.
4. Sort the number from index i+1 to end index. Since this portion would be in reverse sorted order, all we need to do is reverse this portion which takes O(n) time.

Please checkout function findNextGreaterNumber(int[] number) for implementation details. Time complexity of this algorithm is O(n) with O(1) extra space.

Please add comments below in case you have any feedback/queries.


Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.nilesh;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Given a number, finds next greater number of it using same digits. Runs in O(n).
 * @author Nilesh
 */

public class NextGreaterNumber 
{
    private void swap(int[] number, int i, int j)
    {
        int temp  = number[i];
        number[i] = number[j];
        number[j] = temp;
    }
    
    private void sortSubarray(int[] number, int i, int j)
    {
        // for this sub-array, all the digits would be in there reverse sorted position
        while (i < j)
        {
            swap(number, i, j);
            i += 1;
            j -= 1;
        }
    }
    
    public void findNextGreaterNumber(int[] number)
    {
        int lastDigitSeen = number[number.length-1], i, j;
        for (i = number.length-2; i >= 0; i--)
        {
            // if this digit is where the sorted ordering breaks 
            if (lastDigitSeen > number[i])
            {
                break;
            }
            lastDigitSeen = number[i];
        }
        
        if (i >= 0) // we found the digit breaking the sorted ordering
        {
            // find the next greater digit in the right sub-array from number[i+1 to end]
            for (j = number.length-1; j > i; j--)
            {
                if (number[j] > number[i])
                {
                    break;
                }
            }
            
            // swap digits at indices 'i' and 'j'
            swap(number, i, j);
            
            // sort the sub-array - number[i+1 to end]
            sortSubarray(number, i+1, number.length-1);
        }
    }
    
    
    public static void main(String[] args) 
    {
        NextGreaterNumber solution = new NextGreaterNumber();
        
        int[] number = {6,9,3,8,6,5,2};
        
        solution.findNextGreaterNumber(number);
        
        System.out.println("Next greater number is: ");
        for (int i = 0; i < number.length; i++)
        {
            System.out.print(number[i]);
        }
    }
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Nilesh More for compiling current post.

    Nilesh More

    Ninja Programmer