Minimum number of distinct powers of 2 required to express a given binary number | C ++ Program to implement the above approach ; Function to return the minimum distinct powers of 2 required to express s ; Reverse the string to start from lower powers ; Check if the character is 1 ; Add in range provided range ; Initialize the counter ; Check if the character is not 0 ; Increment the counter ; Print the result ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void findMinimum ( string s ) { int n = s . size ( ) ; int x [ n + 1 ] = { 0 } ; reverse ( s . begin ( ) , s . end ( ) ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( s [ i ] == '1' ) { if ( x [ i ] == 1 ) { x [ i + 1 ] = 1 ; x [ i ] = 0 ; } else if ( i and x [ i - 1 ] == 1 ) { x [ i + 1 ] = 1 ; x [ i - 1 ] = -1 ; } else x [ i ] = 1 ; } } int c = 0 ; for ( int i = 0 ; i <= n ; i ++ ) { if ( x [ i ] != 0 ) c ++ ; } cout << c << endl ; } int main ( ) { string str = "111" ; findMinimum ( str ) ; return 0 ; }