Counting Bits

Problem in plain words

Given n, build an array of length n + 1 whose entry i is the number of 1s in the binary form of i. The follow-up asks for a linear-time solution that does not call a built-in popcount on each number.

For n = 4 the answer is [0, 1, 1, 2, 1] (0, 1, 10, 11, 100 in binary).

Intuition

Shifting i right by one bit (i >> 1) drops its lowest bit and keeps everything else. So the 1s in i are the 1s in i >> 1 plus one more if the dropped bit was 1, which is i & 1. Because i >> 1 is always smaller than i, its answer is already in the array when we reach i. Shifts and masks like these are covered in the bitwise operations lesson.

Approach

1. State: bits[i] is the number of set bits in i.
2. Recurrence: bits[i] = bits[i >> 1] + (i & 1).
3. Base case: bits[0] = 0.
4. Order: fill i = 1 to n in increasing order, then return the array.

Dry run

Input: n = 6.

Java solution

class Solution {
    public int[] countBits(int n) {
        int[] bits = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            bits[i] = bits[i >> 1] + (i & 1);
        }
        return bits;
    }
}

Python solution

class Solution:
    def countBits(self, n: int) -> List[int]:
        bits = [0] * (n + 1)
        for i in range(1, n + 1):
            bits[i] = bits[i >> 1] + (i & 1)
        return bits

Complexity

Edge cases and common mistakes

• n = 0: return [0], an array of length 1, not an empty array.
• Operator precedence: in Java and Python, + binds tighter than &, so bits[i >> 1] + i & 1 is wrong. Keep the parentheses around (i & 1).
• Counting each number from scratch: looping over bits for every i is O(n log n). It passes, but it misses the point of the follow-up.