Arrange a binary string to get maximum value within a range of indices | C ++ implementation of the approach ; Storing the count of 1 's in the string ; Query of l and r ; Applying range update technique . ; Taking prefix sum to get the range update values ; Final array which will store the arranged string ; if after maximizing the ranges any 1 is left then we maximize the string lexicographically . ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void arrange ( string s ) { int cc = 0 ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { if ( s [ i ] == '1' ) cc ++ ; } int a [ s . length ( ) + 1 ] = { 0 } ; int qq [ ] [ 2 ] = { { 2 , 3 } , { 5 , 5 } } ; int n = sizeof ( qq ) / sizeof ( qq [ 0 ] ) ; for ( int i = 0 ; i < n ; i ++ ) { int l = qq [ i ] [ 0 ] , r = qq [ i ] [ 1 ] ; l -- , r -- ; a [ l ] ++ ; a [ r + 1 ] -- ; } int len_a = sizeof ( a ) / sizeof ( a [ 0 ] ) ; for ( int i = 1 ; i < len_a ; i ++ ) { a [ i ] += a [ i - 1 ] ; } int zz [ s . length ( ) ] = { 0 } ; for ( int i = 0 ; i < len_a - 1 ; i ++ ) { if ( a [ i ] > 0 ) { if ( cc > 0 ) { zz [ i ] = 1 ; cc -- ; } else break ; } if ( cc == 0 ) break ; } if ( cc > 0 ) { for ( int i = 0 ; i < s . length ( ) ; i ++ ) { if ( zz [ i ] == 0 ) { zz [ i ] = 1 ; cc -- ; } if ( cc == 0 ) break ; } } for ( int i = 0 ; i < s . length ( ) ; i ++ ) cout << zz [ i ] ; cout << endl ; } int main ( ) { string str = "11100" ; arrange ( str ) ; return 0 ; }