Minimum number N such that total set bits of all numbers from 1 to N is at | Python3 implementation of the above approach ; 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
INF = 99999 NEW_LINE size = 10 NEW_LINE def getSetBitsFromOneToN ( N ) : NEW_LINE INDENT two , ans = 2 , 0 NEW_LINE n = N NEW_LINE while ( n > 0 ) : NEW_LINE INDENT ans += ( N // two ) * ( two >> 1 ) NEW_LINE if ( ( N & ( two - 1 ) ) > ( two >> 1 ) - 1 ) : NEW_LINE INDENT ans += ( N & ( two - 1 ) ) - ( two >> 1 ) + 1 NEW_LINE DEDENT two <<= 1 NEW_LINE n >>= 1 NEW_LINE DEDENT return ans NEW_LINE DEDENT def findMinimum ( x ) : NEW_LINE INDENT low = 0 NEW_LINE high = 100000 NEW_LINE ans = high NEW_LINE while ( low <= high ) : NEW_LINE INDENT mid = ( low + high ) >> 1 NEW_LINE if ( getSetBitsFromOneToN ( mid ) >= x ) : NEW_LINE INDENT ans = min ( ans , mid ) NEW_LINE high = mid - 1 NEW_LINE DEDENT else : NEW_LINE INDENT low = mid + 1 NEW_LINE DEDENT DEDENT return ans NEW_LINE DEDENT x = 20 NEW_LINE print ( findMinimum ( x ) ) NEW_LINE