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 [Last updated : February 27, 2023]

Finding 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.

Algorithm for finding the next greatest number from the same set of digits

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:
   1. 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
   2. Now swap the two digits you found in previous step
      So now the number will become 126543
   3. Now sort all the digits from the position next to "x" up to the end in increasing order.
      So the desired output is 126345

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

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

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

/*Method to find the next number greater than the given number*/
void nextNum(char num[], int size)
{
    int i, j;
    for (i = size - 1; i > 0; i--) {
        if (num[i - 1] < num[i])
            break;
    }
    /*if all the digits are in decreasing order then 
the given number the greatest*/
    if (i == 0) {
        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++) {
        /*to find out the next greatest digit after x in num*/
        if (num[j] > x && num[j] < num[smaller]) {
            smaller = j;
        }
    }
    /*Method to swap two digits*/
    swap(&num[smaller], &num[i - 1]);
    /*sort is a predefined method in algorithm */
    sort(num + i, num + size);
    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