How to Find Next Greater Number with Same Set of Digits in C?

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

Problem Statement:

You have given a number. You have to find out next greater number to given number with the same set of digits.

For Example:

Input: 102
Output: 120

Input: 523
Output: 532

Input: 405
Output: 450

It is a tricky question. Logic is all about rearranging digits in the given number and finding the next greater number.

Note: This question was asked in the on-campus Microsoft placement paper.

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

Step 1: Traverse the given number from the 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 the above two steps. (marked in block letters)

Number: 4158762

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

Number: 4152678

So 4152678 is the 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 the given number are sorted in descending order, there is no greater number with the same set of digits.
  Example: Suppose the 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 the given number are sorted in ascending order, you just need to swap last to digits of a given number.
  Example: Suppose the given number is 2356. Swap the last to digits, you will get next greater number as 2365.

C Program to Find the Next Greater Number with Same Set of Digits:

//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

To solve this kind of questions, you have to be great at C/C++ programming concepts.

Complexity & Performance of Program:

You can reduce the complexity of the above program in the following ways.

• In step two we are finding the 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().

What other optimize solution you can program? If you can take this challenge to solve in Python or Java programmer, kindly share your code with me in the comment.

How to Improve your competitive Programming skills?

Do you want to get into one of the top product-based companies like Microsoft, Google, Facebook…?

It is the dream for many of us.

You have to build your competitive programming skills. And there is no shortcut.

Interested in building your competitive programming skills? Take these coding challenges.

Happy Programming!