Minimum number of operations required to sum to binary string S | CPP program to find the minimum number of operations required to sum to N ; Function to return the minimum operations required to sum to a number reprented by the binary string S ; Reverse the string to consider it from LSB to MSB ; initialise the dp table ; If S [ 0 ] = '0' , there is no need to perform any operation ; If S [ 0 ] = '1' , just perform a single operation ( i . e Add 2 ^ 0 ) ; Irrespective of the LSB , dp [ 0 ] [ 1 ] is always 1 as there is always the need of making the suffix of the binary string of the form "11 . . . . 1" as suggested by the definition of dp [ i ] [ 1 ] ; Transition from dp [ i - 1 ] [ 0 ] ; 1. Transition from dp [ i - 1 ] [ 1 ] by just doing 1 extra operation of subtracting 2 ^ i 2. Transition from dp [ i - 1 ] [ 0 ] by just doing 1 extra operation of subtracting 2 ^ ( i + 1 ) ; Transition from dp [ i - 1 ] [ 1 ] ; 1. Transition from dp [ i - 1 ] [ 1 ] by just doing 1 extra operation of adding 2 ^ ( i + 1 ) 2. Transition from dp [ i - 1 ] [ 0 ] by just doing 1 extra operation of adding 2 ^ i ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findMinOperations ( string S ) { reverse ( S . begin ( ) , S . end ( ) ) ; int n = S . length ( ) ; int dp [ n + 1 ] [ 2 ] ; if ( S [ 0 ] == '0' ) { dp [ 0 ] [ 0 ] = 0 ; } else { dp [ 0 ] [ 0 ] = 1 ; } dp [ 0 ] [ 1 ] = 1 ; for ( int i = 1 ; i < n ; i ++ ) { if ( S [ i ] == '0' ) { dp [ i ] [ 0 ] = dp [ i - 1 ] [ 0 ] ; dp [ i ] [ 1 ] = 1 + min ( dp [ i - 1 ] [ 1 ] , dp [ i - 1 ] [ 0 ] ) ; } else { dp [ i ] [ 1 ] = dp [ i - 1 ] [ 1 ] ; dp [ i ] [ 0 ] = 1 + min ( dp [ i - 1 ] [ 0 ] , dp [ i - 1 ] [ 1 ] ) ; } } return dp [ n - 1 ] [ 0 ] ; } int main ( ) { string S = "100" ; cout << findMinOperations ( S ) << endl ; S = "111" ; cout << findMinOperations ( S ) << endl ; return 0 ; }