Minimum number N such that total set bits of all numbers from 1 to N is at | Function to count sum of set bits of all numbers till N ; Function to find the minimum number ; Binary search for the lowest number ; Find mid number ; Check if it is atleast x ; Driver Code
< ? php function getSetBitsFromOneToN ( $ N ) { $ two = 2 ; $ ans = 0 ; $ n = $ N ; while ( $ n ) { $ ans += ( int ) ( $ N / $ two ) * ( $ two >> 1 ) ; if ( ( $ N & ( $ two - 1 ) ) > ( $ two >> 1 ) - 1 ) $ ans += ( $ N & ( $ two - 1 ) ) - ( $ two >> 1 ) + 1 ; $ two <<= 1 ; $ n >>= 1 ; } return $ ans ; } function findMinimum ( $ x ) { $ low = 0 ; $ high = 100000 ; $ ans = $ high ; while ( $ low <= $ high ) { $ mid = ( $ low + $ high ) >> 1 ; if ( getSetBitsFromOneToN ( $ mid ) >= $ x ) { $ ans = min ( $ ans , $ mid ) ; $ high = $ mid - 1 ; } else $ low = $ mid + 1 ; } return $ ans ; } $ x = 20 ; echo findMinimum ( $ x ) ; ? >