Home » C++ programs » C++ Most popular & searched programs

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

Learn: How to **find next greatest number from the same set of digits using a C++ program**?
Submitted by Shubham Singh Rajawat, on June 19, 2017

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.

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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.