0
$\begingroup$

I'm interested in solving a sub problem of the algorithm related question from SO How many binary numbers having given constraints .... The sub problem being, having $x \geq y$

  • determine how many binary numbers of length $x$ have at least $y$ $1$ bits

The immediate algorithm is to go over all $2^x$ binary numbers and count the ones having at least $y$ $1$ bits. Time complexity of such algorithm is $O(2^x)$ or even $O(x2^x)$ since for each number, one has to count the $1$ inside using a loop through all bits (actually $x/2$ on average, but this is not the point).

My target is ideally to find a $O(1)$ algorithm, i.e. a closed formula $f$ such that $\textrm{numbers} = f(x,y)$.

I started with some observations. For $x = 5$, with x being either $0$ or $1$:

y = 1         y = 2    y = 3
1xxxx (2^4)   11xxx    111xx
01xxx (2^3)   101xx    (...)
001xx (2^2)   011xx    Σ = 1x2^2+3x2^1+6x2^0
0001x (2^1)   1001x
00001 (2^0)   0101x
              0011x
Σ = 2^5 - 1   10001
              01001
              00101
              00011

    Σ = 1x2^3+2x2^2+3x2^1+4x2^0

The number of terms is $C_x^y$ and from there it is possible to improve the initial algorithm into parsing only $C_x^y$ elements instead of $2^x$, and as a developer that could make me happy, but, and this is the question,

  • is there a closed formula that gives directly the number of binary numbers of length $x$ having at least $y$ $1$ bits?
$\endgroup$
  • $\begingroup$ I think closed formula for $x \choose y$ + $x \choose y + 1$ + ... + $x \choose x - 1$ + $1$ is the desired answer. $\endgroup$ – f.nasim May 30 '13 at 9:34
  • $\begingroup$ I'm sorry. It has been corrected by someone else. $\endgroup$ – f.nasim May 30 '13 at 9:43
  • 1
    $\begingroup$ @f.nasim, unluckily there is no closed formula for such sums. $\endgroup$ – vonbrand Mar 4 '14 at 15:10
4
$\begingroup$

The required value should be the following:$$\sum_{i=0}^{x-y}\binom{x}{y+i}$$

This is because you need to select $y, (y+1), ..., x$ positions from the total $x$ positions to place $1$'s, and the rest zeroes.

This expression is just a sum of the last $y$ binomial coefficients. As far as I know, there is no general expression for the sum of $k$ binomial coefficients to give you an $O(1)$ answer.

You may find this link helpful for finding a efficient algorithm or a good bound on the sum.

$\endgroup$
  • $\begingroup$ Ok, it seems I cannot get rid of the loop. Let see if someone else comes with a better answer... or, if not, I'll accept this one. Btw, the $C_x^y$ notation is not of usage anymore? $\endgroup$ – Ring Ø May 30 '13 at 10:53
  • 2
    $\begingroup$ Based on the link I am sure there is no closed form expression for the sum. I do not think so; the $\binom{y}{x}$ notation is clearer and easier to read than $C^y_x$. especially when one of the arguments is a longer expression. $\endgroup$ – Milind Jun 1 '13 at 3:56
0
$\begingroup$

You can build your closed formula by adding "number of terms with exactly x '1' bits" and "number of terms with exactly x-1 '1' bits" and so on.

The number of terms with length x and exactly k '1' bits (and hence x-k '0' bits) is $$ \binom {x} {k}=\frac{x!}{(x-k)!k!} $$ Now you just have to add the terms up you are interested in.

$\endgroup$
  • $\begingroup$ Btw, you asked for a O(1) algorithm. Calculating n! is quite expensive, it is in the range of O(n). To come to O(1) you have to use an aproximation. See here for details. $\endgroup$ – stefan.schwetschke May 30 '13 at 10:33
  • $\begingroup$ Thanks, I'm looking for exact values, with the lowest complexity. Please see Milind Hegde's answer who provides a valid answer. $\endgroup$ – Ring Ø May 30 '13 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.