Minimum number of operations required to sum to binary string S | 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
< ? php function findMinOperations ( $ S ) { $ p = strrev ( $ S ) ; $ n = strlen ( $ p ) ; $ dp = array_fill ( 0 , $ n + 1 , array_fill ( 0 , 2 , NULL ) ) ; if ( $ p [ 0 ] == '0' ) { $ dp [ 0 ] [ 0 ] = 0 ; } else { $ dp [ 0 ] [ 0 ] = 1 ; } $ dp [ 0 ] [ 1 ] = 1 ; for ( $ i = 1 ; $ i < $ n ; $ i ++ ) { if ( $ p [ $ 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 ] ; } $ S = "100" ; echo findMinOperations ( $ S ) . " STRNEWLINE " ; $ S = "111" ; echo findMinOperations ( $ S ) . " STRNEWLINE " ; return 0 ; ? >