13

This was an interview question. The original questions asks:

Given a positive integer N, count the number of 1's in each integer from 0 to N, and return the count in an array of size N+1. Do it in O(n) time.

An Example would be:

Given 7, then return [0, 1, 1, 2, 1, 2, 2, 3]

Of course, the easiest way is to create a loop counting 1's for every integer, but that would be O(kn) time, with k as the size of the integers in bits. So either there's a way to count the number of 1's of an integer in O(1) time, or there's a way to directly generate the count going from 0 to N. I'm sure both methods exist, but can't figure out either.

1
  • 1
    @Idos I think this is a sufficiently different problem from the one described in the linked answer that this wouldn't count as a duplicate. Mar 24, 2017 at 19:37

3 Answers 3

14

Here's a nice little observation that you can use to do this in time O(n). Imagine you want to know how many 1 bits are set in the number k, and that you already know how many 1 bits are set in the numbers 0, 1, 2, ..., k - 1. If you can find a way to clear any of the 1 bits that are set in the number k, you'd get some smaller number (let's call it m), and the number of bits set in k would then be equal to one plus the number of bits set in m. So provided that we can find a way to clear any 1 bit from the number k, we can use this pattern to solve the problem:

result[0] = 0  // No bits set in 0
for k = 1 to n:
    let m = k, with some 1 bit cleared
    result[k] = result[m] + 1

There's a famous bit twiddling trick where

 k & (k - 1)

yields the number formed by clearing the lowest 1 bit that's set in the number k, and does so in time O(1), assuming that the machine can do bitwise operations in constant time (which is usually a reasonable assumption). That means that this pseudocode should do it:

result[0] = 0
for k = 1 to n:
    result[k] = result[k & (k - 1)] + 1

This does O(1) work per number O(n) total times, so the total work done is O(n).

Here's a different way to do this. Imagine, for example, that you know the counts of the bits in the numbers 0, 1, 2, and 3. You can use this to generate the counts of the bits of the numbers 4, 5, 6, and 7 by noticing that those numbers have bitwise representations which are formed by taking the bitwise representations of 0, 1, 2, and 3 and then prepending a 1. Similarly, if you then knew the bit counts of 0, 1, 2, 3, 4, 5, 6, and 7, you could generate the bit counts of 8, 9, 10, 11, 12, 13, 14, and 15 by noting that they too are formed by prepending a 1 bit to each of the lower numbers. That gives rise to this pseudocode, which for simplicity assumes that n is of the form 2k - 1 but could easily be adapted for a general n:

result[0] = 0;
for (int powerOfTwo = 1; powerOfTwo < n; powerOfTwo *= 2) {
    for (int i = 0; i < powerOfTwo; i++) {
        result[powerOfTwo + i] = result[i] + 1;
    }
}

This also runs in time O(n). To see this, notice that across all iterations of all the loops here, each entry in the array is written to exactly once, with O(1) work done to determine which value is supposed to be put into the array at that slot.

6
  • 2
    While this is definitely a nice speed up, I am not sure it really changes the asymptotic complexity. If we regard the number of bits in an integer as constant also the OP's naive algorithm is already O(n). If we don't do that (i.e. number of bits is O(log n)) then these algorithms will take O(n log n) time, again the same as OP's naive algorithm.
    – Henry
    Mar 24, 2017 at 20:03
  • 1
    @Henry If we assume a transdichotomous model where operations on a machine word take time O(1), but the number of bits in a machine word are assumed to be O(log n), then both of these approaches will take time O(n) (independent of the number of bits) because they only use word operations. Counting bits one at a time using the naive approach takes O(log n) word operations, so its runtime would be O(n log n). Those approaches would also be slower in practice. Mar 24, 2017 at 20:33
  • Nice trick! I noticed the 2^k - 1 relation and was trying to deduce a general formula for something like this, but this is perfect!
    – bli00
    Mar 24, 2017 at 20:55
  • 2
    @henry: even if we use a bit counting model of time complexity (which is rarely helpful imho), the amortised cost of repeatedly incrementing a number is O(1), because half the time, only one bit is examined; one quarter of the time, it's two bits; one eighth of the time three bits, etc. A similar argument applies to adding one to a series of numbers for most distribution s of the series. You could argue that a bit copy is necessary, but even then the size of the bit count in bits is log log n, not log n.
    – rici
    Mar 24, 2017 at 22:01
  • @templatetypedef There is no doubt, that the naive approach is much slower. The question is about time-complexity. I agree to your analysis but to assume O(1) for a "bitwise and" or an "add" and at the same time O(log n) for counting bits does not feel right to me.
    – Henry
    Mar 25, 2017 at 5:01
4

Much simpler answer:

Let x be an array of length k+1 and x[i] has the number of set bits in i.

x[0] = 0
for i=1:k
    x[i] = x[i>>1] + i&1
3

We start by manually evaluating the bit count for some small numbers. We note a recurrence relation between the bit count of n and previous results:

 n: | count(n): | recurrence:
==============================
  0 |        0 |
  1 |        1 |
------------------------------
 10 |        1 | =  count(0) + 1
 11 |        2 | =  count(1) + 1
------------------------------
100 |        1 | =  count(0) + 1
101 |        2 | =  count(1) + 1
110 |        2 | = count(10) + 1
111 |        3 | = count(11) + 1
...

Given all bit counts up to 2 = 2¹, we can compute the bit counts up to 4 = 2² by adding 1. Given the bit counts up to 4 = 2², we can compute the bit counts up to 8 = 2³ by adding 1. We generalize this to the k-th power of two and can come up with following exemplary implementation:

// Counts and returns number of enabled bits for integers 0 - n:
function count_bits(n) {
  let count = new Array(n);
  count[0] = 0;
  for (let i = 1, j = 0, k = 1; i <= n; ++i, ++j) {
    if (i == 2**k) { // k-th bit of i has been enabled
      k++;
      j = 0;
    }
    count[i] = count[j] + 1;
  }
  return count;
}

// Example:
console.log(count_bits(17).join());

We note that all operations involved are incrementing by one, random array access, copying array elements and checking the k-th bit of loop increment i via i == 2**k which could be rewritten as i & 1 << k or - for arbitrary precision of i - as a random array access.

Assuming that all primitive operations listed above are in O(1) on our machine, the total runtime complexity is in O(n).

This would equally hold for arbitrary precision integers - where incrementing has an average runtime complexity of O(1) - unless copying count[i] = count[j] + 1 takes more than constant time. As this is unfortunately the case for arbitrarily large integers, our runtime complexity is in O(n log(log(n))) as we need O(log(log(n))) space to store the bit count of n.

3
  • My apologies if I'm mistaken, but isn't the algorithm you've described here the second algorithm I proposed in my answer? Mar 25, 2017 at 0:50
  • 1
    @templatetypedef Yes it is, it is the same as described here.
    – le_m
    Mar 25, 2017 at 0:53
  • @templatetypedef By the way, do you agree on O(n log(log(n))) for arbitrary large input?
    – le_m
    Mar 25, 2017 at 0:58

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.