Number of binary representations Calculate the amount of numbers from $1$ to $N$ in the binary representation of which contains exactly $K$ zeroes.
For example:
for $N = 18$ which is $10010$ in binary representation and $K = 3$ the answer is $3$ $10001;10010;1000$
 A: Let $k = \lfloor \log_2{N} \rfloor$ and let $n = 2^ka_k + 2^{k-1}a_{k-1} + \dotsb + a_0$ in binary, where $n$ is a number satisfying the given conditions. We make two cases on $n$: $a_k = 0$ and $a_k = 1$.
If $a_k = 0$, then to get a number with $K$ significant zeroes in the digits $a_0, a_1, \dotsc, a_{k-1}$, we simply have to select $K$ places for the zeroes and fill the rest with ones. We cannot put a zero in the $k-1$th place, thus we can do this in $\binom{k-1}{K}$ ways. The number formed is obviously less than $N$.
If $a_{k-1} = 1$, then consider the number of zeroes in the binary representation of $N$. Call this number $c$. If $c > K$, there are no numbers with $a_{k-1} = 1$ and $K$ significant zeroes; else, out of the remaining $k - c$ digits which are 1, convert any $K - c$ to 0: there are $\binom{k - c}{K - c}$ ways to do this.
Thus, the final answer is:


*

*If $c > K$, there are $\binom{k-1}{K}$ such numbers

*If $c \leq K$, there are $\binom{k-1}{K} + \binom{k  - c}{K - c}$ such numbers


where $c$ is the number of zeroes in the binary representation of $N$, and $k$ is $\lfloor \log_2{N} \rfloor$.
