Minimum number of distinct powers of 2 required to express a given binary number | Java 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
import java . util . * ; class GFG { static void findMinimum ( String s ) { int n = s . length ( ) ; int [ ] x = new int [ n + 1 ] ; StringBuilder s2 = new StringBuilder ( s ) ; s2 . reverse ( ) ; String s3 = s2 . toString ( ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( s3 . charAt ( i ) == '1' ) { if ( x [ i ] == 1 ) { x [ i + 1 ] = 1 ; x [ i ] = 0 ; } else if ( 1 <= i && ( i & 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 ++ ; } System . out . println ( c ) ; } public static void main ( String [ ] args ) { String str = "111" ; findMinimum ( str ) ; } }