Counting Bits

Given a non-negative integer n, build a list ans of length n + 1 where ans[i] is the number of 1 digits in the binary representation of i, for every i from 0 up to n.

For instance, 6 is 110 in binary, so ans[6] = 2.

Counting the bits of each number separately takes O(n log n) time. Try to produce the whole list in O(n) time by reusing answers you have already computed, without relying on a built-in popcount function.

Example 1

Example 2

Example 3

Constraints

• 0 <= n <= 105

Pattern Path · Math, Bits & Strings · problem 29 of 169

Start simple

Count the bits of every i from 0 to n independently by repeatedly checking the lowest bit: O(n log n) time.

The key idea

This is a small dynamic program in which each answer is built from an earlier one. The binary form of i >> 1 (that is, i // 2) is the binary form of i with its last bit removed. For example, 13 is 1101 and 6 is 110.

So i has the same number of ones as i >> 1, plus one more if the removed bit was a 1, which is i & 1:

ans[i] = ans[i >> 1] + (i & 1)

Since i >> 1 < i for every i ≥ 1, filling the list in increasing order guarantees the value we need is ready, starting from ans[0] = 0. Each entry costs O(1), so the whole list takes O(n).

An equally valid recurrence uses the trick that i & (i - 1) clears the lowest set bit: ans[i] = ans[i & (i - 1)] + 1.

Complexity

• Time: O(n)
• Space: O(1) extra (the output list is O(n))

Python

class Solution:
    def countBits(self, n: int) -> List[int]:
        ans = [0] * (n + 1)
        for i in range(1, n + 1):
            # i >> 1 is i without its last bit; i & 1 is that last bit
            ans[i] = ans[i >> 1] + (i & 1)
        return ans

JavaScript

var countBits = function(n) {
  const ans = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    // i >> 1 is i without its last bit; i & 1 is that last bit
    ans[i] = ans[i >> 1] + (i & 1);
  }
  return ans;
};

What the interviewer is checking

It checks whether you can spot a recurrence between a number and a smaller one, i.e. dynamic programming over bit patterns, rather than recomputing each count.

Mistakes to avoid

• Returning a list of length n instead of n + 1 (0 through n inclusive).
• Mixing up operator precedence: in many languages i & 1 needs parentheses when combined with +.
• Using a built-in popcount and claiming O(n) when the follow-up asked for none.

Follow-ups to expect

• Use the lowest-set-bit recurrence instead. (ans[i & (i - 1)] + 1.)
• Total number of 1 bits from 0 to n without the list. (Count per bit position.)
• Count bits of a single 32-bit number. (Kernighan or bit tricks.)

In real software

Precomputed popcount tables speed up bitboard chess engines, Hamming distance in similarity search, and set-size calculations in bitmap indexes.

Practice next