StackStalk
  • Home
  • Java
    • Java Collection
    • Spring Boot Collection
  • Python
    • Python Collection
  • C++
    • C++ Collection
    • Progamming Problems
    • Algorithms
    • Data Structures
    • Design Patterns
  • General
    • Tips and Tricks

Monday, March 11, 2013

Next number formed from permutation of digits

 March 11, 2013     Programming problems in CPP     No comments   

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.

Approach:
  • 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)
        {
            digitnumber--;
            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;
                    break;
                }
            }
            // 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;
}
Output:-
input: 3397421 
output: 3412379
  • Share This:  
Newer Post Older Post Home

0 comments:

Post a Comment

Follow @StackStalk
Get new posts by email:
Powered by follow.it

Popular Posts

  • Avro Producer and Consumer with Python using Confluent Kafka
    In this article, we will understand Avro a popular data serialization format in streaming data applications and develop a simple Avro Produc...
  • Monitor Spring Boot App with Micrometer and Prometheus
    Modern distributed applications typically have multiple microservices working together. Ability to monitor and manage aspects like health, m...
  • Server-Sent Events with Spring WebFlux
    In this article we will review the concepts of server-sent events and work on an example using WebFlux. Before getting into this article it ...
  • Implement caching in a Spring Boot microservice using Redis
    In this article we will explore how to use Redis as a data cache for a Spring Boot microservice using PostgreSQL as the database. Idea is to...
  • Python FastAPI microservice with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Spring Boot with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Getting started with Kafka in Python
    This article will provide an overview of Kafka and how to get started with Kafka in Python with a simple example. What is Kafka? ...
  • Getting started in GraphQL with Spring Boot
    In this article we will explore basic concepts on GraphQL and look at how to develop a microservice in Spring Boot with GraphQL support. ...

Copyright © StackStalk