Find Next Greater Number with Same Set of Digits

This is Quiz question as well as asked in many placement interviews to write code to find next greater number with same set of digits of a given number. You have given a number. You have to find out next greater number to given number with the same set of digits.

It is the tricky question. Logic is all about rearranging digits in given number and finding next greater number. If you get the logic, it is easy to figure out.

Note: This question has asked in on campus Microsoft placement paper .

Algorithm to find Find Next Greater Number with Same Set of Digits:

Step 1: Traverse the given number from rightmost digit. Keep traversing till you get a digit which is smaller than the previously traversed digit.

Consider if the given input number is “4128765”, Here while traversing from right, stop at 2 because 2 is smaller than next digit 8. If there is no such digit, there is no greater number.

Number: 4128765

Step 2: Now consider all the digits right side of 2. Find the smallest digit among them. Here smallest digit that resides right side of 2 is 5.

Number: 4128765

Step 3: Swap the two digits found in above two steps. (marked in block letters)

Number: 4158762

Step 4: Sort all the digits right side of 5.

Number: 4152678

So 4152678 is next greater number of  4128765 with the same set of digits.

Special Cases to Find Next Greater Number with Same Set of Digits:

• If your digits in given number are sorted in descending order, there is no greater number with the same set of digits.
  Example: Suppose given number is 7432. It is the greatest number in the set of (7, 4, 3, 2). So there is no next greater number.
• If your digits in given number are sorted in ascending order, you just need to swap last to digits of a given number.
  Example: Suppose given number is 2356. Swap the last to digits, you will get next greater number as 2365.

Code:

// C++ program to find the Next Greater Number 
// with Same Set of Digits of a Given Number
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
// Swap is Utility function to swap two characters in the string
void swap(char *strA, char *strB)
{
    char temp = *strA;
    *strA = *strB;
    *strB = temp;
}
 
//Given a number as a char array strNumber[], 
//This function finds the next greater number.  
//It modifies the same array to store the result as we are using call by reference mechanism 

void  findNextNumber(char strNumber[], int nLen)
{
    int i, j;
 
    // Step 1: Start from the right most digit and find the first digit // which is smaller than the digit next to it.
    for (i = nLen-1; i > 0; i--)
        if (strNumber[i] > strNumber[i-1])
           break;
 
    // If no such digit is there, then all digits might be in descending order
    // In this case there is no greater number possible with same set of digits
    if (i==0)
    {
        cout << "Next number is not possible";
        return;
    }
 
    // Step 2: Find the smallest digit on right side of (i-1)'th digit // that is greater than strNumber[i-1]
    int x = strNumber[i-1], nSmallestLoc = i;
    for (j = i+1; j < nLen; j++) if (strNumber[j] > x && strNumber[j] < strNumber[nSmallestLoc])
            nSmallestLoc = j;
 
    // Step 3: Swap the above found smallest digit with number[i-1]
	// using utilit function swap
    swap(&strNumber[nSmallestLoc], &strNumber[i-1]);
 
    // Step 4: Sort the all the digits in strNumber after (i-1) in ascending order
    sort(strNumber + i, strNumber + nLen);
    return;
}
 
// Main Driver program to test function findNextNumber()
int main()
{
    char strNumber[] = "454652";
	cout<<"Next Greater Number with Same Set of Digits";
	cout<<"\nGiven Number is "<<strNumber;
    int nLen = strlen(strNumber);
    findNextNumber(strNumber, nLen);
	cout<<"\nNext greater number is "<<strNumber;	
    return 0;
}

Output:

Next Greater Number with Same Set of Digits
Given Number is 454652
Next greater number is 455246

Complexity & Performance of Program:

You can reduce the complexity of above program in following ways

• In step two we are finding smallest number. We can improve performance by binary searching, instead of linear search.
• In step four, you can use the most optimized sorting technique.
• You can also improve the performance by checking special cases before calling findNextNumber().