Minimum number N such that total set bits of all numbers from 1 to N is at | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define INF  99999 NEW_LINE #define size  10 NEW_LINE int getSetBitsFromOneToN ( int N ) { int two = 2 , ans = 0 ; int n = N ; while ( n ) { ans += ( N / two ) * ( two >> 1 ) ; if ( ( N & ( two - 1 ) ) > ( two >> 1 ) - 1 ) ans += ( N & ( two - 1 ) ) - ( two >> 1 ) + 1 ; two <<= 1 ; n >>= 1 ; } return ans ; } int findMinimum ( int x ) { int low = 0 , high = 100000 ; int ans = high ; while ( low <= high ) { int mid = ( low + high ) >> 1 ; if ( getSetBitsFromOneToN ( mid ) >= x ) { ans = min ( ans , mid ) ; high = mid - 1 ; } else low = mid + 1 ; } return ans ; } int main ( ) { int x = 20 ; cout << findMinimum ( x ) ; return 0 ; }