Partition the digits of an integer such that it satisfies a given condition | C ++ implementation of the approach ; Function to generate sequence from the given string ; Initialize vector to store sequence ; First add all the digits of group A from left to right ; Then add all the digits of group B from left to right ; Return the sequence ; Function that returns true if the sequence is non - decreasing ; Initialize result ; Function to partition the digits of an integer such that it satisfies the given conditions ; Convert the integer to string ; Length of the string ; Array to store the digits ; Storing the digits of X in array ; Initialize the result ; Loop through the digits ; Put into group A if digit less than D ; Put into group B if digit greater than D ; Put into group C if digit equal to D ; Loop through the digits to decide for group C digits ; Set flag equal to true if group B digit present ; If flag is true put in group A or else put in B ; Generate the sequence from partition ; Check if the sequence is non decreasing ; Return - 1 if no such partition is possible ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > makeSeq ( string s , int a [ ] ) { vector < int > seq ; for ( int i = 0 ; i < s . size ( ) ; i ++ ) if ( s [ i ] == ' A ' ) seq . push_back ( a [ i ] ) ; for ( int i = 0 ; i < s . size ( ) ; i ++ ) if ( s [ i ] == ' B ' ) seq . push_back ( a [ i ] ) ; return seq ; } bool checkSeq ( vector < int > v ) { bool check = true ; for ( int i = 1 ; i < v . size ( ) ; i ++ ) if ( v [ i ] < v [ i - 1 ] ) check = false ; return check ; } string digitPartition ( int X ) { string num = to_string ( X ) ; int l = num . size ( ) ; int a [ l ] ; for ( int i = 0 ; i < l ; i ++ ) a [ i ] = ( num [ i ] - '0' ) ; for ( int D = 0 ; D < 10 ; D ++ ) { string res = " " ; for ( int i = 0 ; i < l ; i ++ ) { if ( a [ i ] < D ) res += ' A ' ; else if ( a [ i ] > D ) res += ' B ' ; else res += ' C ' ; } bool flag = false ; for ( int i = 0 ; i < l ; i ++ ) { if ( res [ i ] == ' B ' ) flag = true ; if ( res [ i ] == ' C ' ) res [ i ] = flag ? ' A ' : ' B ' ; } vector < int > seq = makeSeq ( res , a ) ; if ( checkSeq ( seq ) ) return res ; } return " - 1" ; } int main ( ) { int X = 777147777 ; cout << digitPartition ( X ) ; return 0 ; }