C++ Rearrange the digits to form minimum possible number














































C++ Rearrange the digits to form minimum possible number



Problem Description:

Given a number N, find the smallest number which can be obtained by rearranging the digits of N. The generated number should not have any leading zeroes.

THIS PROBLEM HAS BEEN ASKED IN FLIPKART FREQUENTLY

Note*:: Both input and output are to be performed using the string data type.


Example 1:

Given: N = 746903
Output: 304679


Example 2:

Input: N = 44020
Output: 20044


Time Complexity: O(log N)
Auxiliary Space: O(1)


Code::

#include<bits/stdc++.h>
using namespace std;
class solve
{
public:
    string smallestnumberpossible(string N)
    {
        stringstream ss(N); //stream buffer to manipulate string
        int x = 0; 
        ss>>x;  //allows convertion from string to int
        int count=0,s1=-99999;
        vector<int> v; //allows data storage without any predefined memory allocation
        while(x){
            int t=x%10; //initialized a temporary variable with last digit
            if(t<s1)
                s1=t;
            if(t==0)
                ++count; //counter for number of zeroes
            v.push_back(t); //storing t in vector v
            x=x/10; // diving by 10 so that we can operate on adjacent digit by shifting it to most significant position
        }
        sort(v.begin(),v.end()); // sort function in vector
        if(count!=0){
            swap(v[count],v[0]); // swap function in vector
        }
        ostringstream oss; //output string stream
        if(!v.empty()){
        copy(v.begin(), v.end()-1,ostream_iterator<int>(oss, ""));//converting vector to string by copying into string
        oss<<v.back();
      }
        v.clear();
    return oss.str(); //returning string via string function
    }
    int main(){
    string N;
     cin>>N;
     solve obj;
     string res=obj.smallestnumberpossible(N);
     cout<<res<<endl;
    return 0;
}
};


 


Output::



Comments