Given a number n, find the smallest number that has same set of digits as n and is greater than n. If x is the greatest possible number with its set of digits, then print “not possible”.
EXAMPLES : Input: n = "218765" Output: "251678" Input: n = "1234" Output: "1243" Input: n = "4321" Output: "Not Possible" Input: n = "534976" Output: "536479"
Following are few observations about the next greater number.
1) If all digits sorted in descending order, then output is always “Not Possible”.
For example, 4321. 2) If all digits are sorted in ascending order, then we need to swap last two digits.
For example, 1234.
3) For other cases, we need to process the number from rightmost side (why? because we need to find the smallest of all greater numbers)
i) the first place where the left-digit is less-than the right-digit in last example 534976, its 4.
ii) find the smallest digit larger than 4 to the right , its 6.
iii) place it to the left of 4
iv) sort the digits to the right of 6.
CODE
#include<iostream>
#include<string.h>
using namespace std;
bool nxt(char *s);
int main()
{
char *str=new char[50];
cout<<"ent the number: ";
gets(str);
bool f=nxt(str);
if(f)
cout<<"next greater num= "<<str<<endl;
else
cout<<"not possible\n";
return 0;
}
bool nxt(char *s)
{
int len=strlen(s);
int i;
for(i=len-2;i>=0;i--)
{
if(s[i]<s[i+1])
break;
}
if(i== -1)
return false;
else
{
int min=1111111, pos;
for(int j=i+1;j<len;j++)
{
if(s[j]>s[i] && min>s[j])
{
min=s[j];
pos=j;
}
}
char temp;
temp=s[i];
s[i]=s[pos];
s[pos]=temp;
int start=i+1, end=len-1;
while(start<end)
{
temp=s[start];
s[start]=s[end];
s[end]=temp;
start++;
end--;
}
return true;
}
}
