Find the smallest number $n$ such that the sum of set bits(1's in binary representation) for all number from $1$ to $n$ is greater than a given integer $X$ where $1 \lt X \lt 10^{18}$
Example for $X = 5$, the answer is $4$,since sum of $1$ to $4$ is $5$
$0001 = 1$
$0010 = 1$
$0011 = 2$
$0100 = 1$
From this answer
$F(n) = F(m) + F(n - m - 1) + (n - m)$ where $m = 2^k - 1$ and $m < n$
I can only think of looping though all possible integers in the range and find which is the smallest one that satisfies this condition.
How do I solve this without looping though the entire range of possible answers.
Let $P_X(n)$ be true if the sum of set bits of the numbers from 1 to $n$ is greater or equal to $X$. Then $P_X(n)$ true implies $P_X(n')$ true for any $n' > n$. Therefore you can apply binary search: suppose you are searching the interval $[a,b]$. Let $m=\lfloor(a+b)/2\rfloor$. If $P_X(m)$ is true, then you can reduce your interval to $[a,m]$; if it is false, you can reduce your interval to $[m+1,b]$.