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$
3
  • $\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
    Commented May 30, 2013 at 9:34
  • $\begingroup$ I'm sorry. It has been corrected by someone else. $\endgroup$
    – f.nasim
    Commented May 30, 2013 at 9:43
  • 1
    $\begingroup$ @f.nasim, unluckily there is no closed formula for such sums. $\endgroup$
    – vonbrand
    Commented Mar 4, 2014 at 15:10

2 Answers 2

5
$\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$
2
  • $\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$
    – Déjà vu
    Commented May 30, 2013 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$ Commented Jun 1, 2013 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$
2
  • $\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$ Commented May 30, 2013 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$
    – Déjà vu
    Commented May 30, 2013 at 10:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .