Monday, March 11, 2013

Write a program to find the next number formed from permuting the digits in a given number

For example if the given number is 312, then the next number is 321 if you permute 1,2,3.
  • Start to looking at digits one by one from 1's digit towards left.
  • Check that digit value to its immediate left digit value. If that digit value is higher than the digit on the immediate left side of it, then stop. Let us say kth position digit is higher than (k+1)th position digit (K+1 is the place left of kth). 
  • Now look for digit on the visited list (all the k places) and find out a digit which is just higher than the (k+1)th digit. Exchange those two digits and then place all the k digits in increasing order (they are already in order but in decreasing). 

C++ program to find the next number formed from permuting the digits

#include <iostream>
using namespace std;

const int MAX_SIZE=10;

int nextPermutedNum(int aInput)
    int input = aInput;
    int buffer[MAX_SIZE];
    int prev = input % 10;
    int digitnumber = 0;
    buffer[digitnumber++] = prev;
    while (input > 9)
        input /= 10;
        int next = input % 10;
        buffer[digitnumber++] = next;
        if (next < prev)
            int newnum = input/10;
            newnum *= 10;
            // find and swap with next big number from the visited digits.
            for (int i=0;i<digitnumber;i++)
                if (next<buffer[i])
                    newnum += buffer[i];
                    buffer[i] = next;
            // fill all the remaining digit places with increasing order of visited numbers.
            for (int i =0;i< digitnumber;i++)
                newnum *= 10;
                newnum += buffer[i];
            return newnum;
        prev = next;
    return aInput;

int main()
    int num = 3397421;
    cout << "input: " << num << endl;
    int output = nextPermutedNum(num);
    cout << "output: " << output << endl;
    return 0;

input: 3397421 
output: 3412379 


Post a Comment

Contact Form


Email *

Message *

Back to Top