Find the next greater number from the same set of digits in C++

In this tutorial, we are going to find the next greater number from the same set of digits in C++. We can form many numbers by the different combination of a given set of digits in a number. Finding a number which is just greater than the given number from such set is the motive of our program. If you are searching for such a solution then you are at right place. Here I am going to give a very easy and detailed explanation.

Also, read:

How to print arrays mirror image of 2D array (3X3) in C++

Next greater number from the same sequence of digits in C++

Let us consider an example:

If a user enters a number 312. Now the possible combinations for these digits are 123, 132, 312 and 321. We are required to give the next greater number in the sequence i.e. 321 as an output.

Enter a number: 312
Next greater number in the sequence is: 321

Algorithm




Following is the algorithm which will be applicable in every case to implement the program in C++.

  1. If the digits of the number are all in descending order then that number is the greatest number possible in the combination. In such case, it is not possible to calculate the next greater number.
  2. If they are in increasing order then just swap the last two digits.
  3. In any other case, our common procedure will be applicable, starting from the last digit of number find a digit which is smaller than the just previous one. (e.g. The digit 2 in 1284 is smaller than 8 as required.)
  4. This smaller digit is now swapped with a number which is just greater than this digit but not the largest one (The number 2 in 1284 is swapped with 4 not with 8 as per condition).
  5. Finally, sort the digits present next to this number in ascending order.

Code

Firstly the number is stored in an integer array for better manipulation. Then check if the digits are in decreasing order, if not then find the follow the algorithm point number 3 i.e. find the digit smaller than previous one from ending. In this code, the value is stored in variable “small“.

for(pos=length-1;pos>0;pos--){
    if(num[pos]>num[pos-1])
        break;
}

if(pos==0){             // if digits of numbers are in decreasing order
    cout<<"This is already the greatest number of all the possible combinations.";
    return 0;
}else
    small=num[pos-1];

The step is to find the digit in the number which is next greater than this.It is done like this. This digit is stored in the variable “nextbig” and the index of this digit is stored in “pos2“.

for(int i=pos;i<length;i++){
    if(num[i]>small&&num[i]<nextbig){
        nextbig=num[i];
        pos2=i;
    }
}

Then the swapping is done in a very common and well-known method i.e. with using a temporary variable. You can also do this by another method explained in the link below.

How to swap two numbers without using a third variable in C++

After the swapping is complete the final part is sorting the remaining digits by any method. The number which is now with us is the required value.

Below is the final and complete working code for finding the greater number from the same set of digits in C++. I have written this in CodeBlocks v 16.01. I recommend you too the same or else you can run this on other C++ IDE with slight modifications only.

#include <iostream>
#include<string.h>

using namespace std;

int main()
{
    char number[15];
    int num[15];

    cout<<"Enter a number: ";       //input value
    cin>>number;

    int i,length=strlen(number);
    for(i=0;i<length;i++){              // conversion of character array to char array on the basis of ASCII values
            int n=number[i];
        switch(n){
            case 48:num[i]=0;break;
            case 49:num[i]=1;break;
            case 50:num[i]=2;break;
            case 51:num[i]=3;break;
            case 52:num[i]=4;break;
            case 53:num[i]=5;break;
            case 54:num[i]=6;break;
            case 55:num[i]=7;break;
            case 56:num[i]=8;break;
            case 57:num[i]=9;break;
        }
    }

    int pos;
    int small,nextbig=9;


    for(pos=length-1;pos>0;pos--){
        if(num[pos]>num[pos-1])
            break;
    }

    if(pos==0){             // if digits of numbers are in decreasing order
        cout<<"This is already the greatest number of all the possible combinations.";
        return 0;
    }else
        small=num[pos-1];

    int pos2;
    for(int i=pos;i<length;i++){
        if(num[i]>small&&num[i]<nextbig){
            nextbig=num[i];
            pos2=i;
        }
    }

    swap(num[pos-1],num[pos2]);

    for(i=pos;i<length;i++){
        for(int j=pos;j<=length-i;j++){
            if(num[j]>num[j+1]){
                int temp=num[j];
                num[j]=num[j+1];
                num[j+1]=temp;
            }
        }
    }

    cout<<"Next greater number in the sequence is: ";
    for(i=0;i<length;i++)
        cout<<num[i];
    return 0;
}

void swap(int &a,int &b){
    int temp;
    temp=a;
    a=b;
    b=temp;
}

Outputs Examples

Enter a number: 1248
Next greater number in the sequence is: 1284
Enter a number: 453135
Next greater number in the sequence is: 453153

You can drop your queries in the comment box below.


Leave a Reply

Your email address will not be published. Required fields are marked *