Q:

C++ program to find the next greatest number from the same set of digits

mahmoud2506
Save to bookmark
|
2022-05-04
|
  266 
0

C++ program to find the next greatest number from the same set of digits

As clear from the name we have to find a number which is smallest in all the number greater than the given number with same set of digits.

For example:
If n = 123456
Then the next number greater than this is 123465

If n = 7531
Then no number is possible which is greater than this with same set of digits.

Same set of digits means that we can only use 7,5,3,1 to form a new number as given in the above example.

C++ programming, exam questions, C++ programming exam-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-05-04
need an explanation for this answer? contact us directly to get an explanation for this answer

Algorithm:

There are three cases that we have to keep in mind:

1) If all the digits are in decreasing order then no number greater than the given number is possible.

2) If all the digits are in increasing order then we just need to swap the last two digits to find the next greatest number.

3) This is the most important and of course the general case, this can be solved by doing following steps:

A) Traverse the given number from the last digit until you find a digit smaller than its preceding digit. If you did not find it then number greater than the given number is not possible, if you find that digit ("say x") then from x traverse to the right until you find a digit smallest in all the digits present on the right side of "x" but greater than "x".
For example:
If number is 125643
Then x will be 5 as 5 is smaller than 6
And the next digit will be 6 as 6 is the only digit on the right which is greater than 5

B) Now swap the two digits you found in previous step
So now the number will become 126543

C) Now sort all the digits from the position next to "x" up to the end in increasing order.
So the desired output is 126345

Consider the program:

#include<iostream>
#include<algorithm>         
using namespace std;

void swap(char *x,char *y)  /*Method to swap two digits*/
{
	char temp=*x;
	*x=*y;
	*y=temp;
}

void nextNum(char num[],int size)  /*Method to find the next number greater than the given number*/
{
	int i,j;
	for(i=size-1;i>0;i--)	
	{
		if(num[i-1]<num[i])  
		    break;
	}
	
	if(i==0)            /*if all the digits are in decreasing order then the given number the greatest*/
	{
		cout<<"No number greater than this is possible from the same set of digits";
		return;
	}
	int x=num[i-1],smaller=i;
	for(j=i+1;j<size;j++)
	{
		if(num[j]>x && num[j]<num[smaller])  /*to find out the next greatest digit after x in num*/
		{
			smaller=j;
		}
	}
	swap(&num[smaller],&num[i-1]);    /*Method to swap two digits*/
	sort(num+i,num+size);            /*sort is a predefined method in algorithm */
	for(int i=0;i<size;i++)
	{
		cout<<num[i];
	}
	return ;
}

int main()
{
	int n;
	cout<<"Enter the size of the number :";
	cin>>n;
	char number[n];
	cout<<"Enter the number :";
	for(int i=0;i<n;i++)
	{
		cin>>number[i];
	}
	nextNum(number,n);
	return 0;
}

Output

FIRST INPUT:
Enter the size of the number :10
Enter the number :1823471897
1823471978


SECOND INPUT:
Enter the size of the number :6
Enter the number :975431
No number greater than this is possible from the same set of digits

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Most popular and Searched C++ solved programs with Explanation and Output
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
C++ program to find Fibonacci number using differe... >>
<< C++ program to convert number to word (up to four ...