This is a 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.
Step 1: Traverse the given number from the rightmost digit. Keep traversing till you get a digit that is smaller than the previously traversed digit.
Consider if the given input number is “4128765”, Here while traversing from the right, stop at 2 because 2 is smaller than the 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.
//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 question, you have to be great at C/C++ programming concepts.
You can reduce the complexity of the above program in the following ways.
What other optimized 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.
Do you want to get into one of the top product-based companies like Microsoft, Google, or Facebook…?
It is a 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!
I am complete Python Nut, love Linux and vim as an editor. I hold a Master of Computer Science from NIT Trichy. I dabble in C/C++, Java too. I keep sharing my coding knowledge and my own experience on <b>CSEstack.org</b> portal.
Here is the simple solution to remember:
1. Find the two smallest elements from the right side and swap them.
2. Get all right side elements of the second smallest element and sort them.