338. Counting Bits - Detailed Explanation

Given an integer n, return an array of length n + 1 where the entry at index i is the number of ones in the binary representation of i. The naive answer counts the bits of every number separately, which costs O(n log n). The question explicitly asks whether you can do it in linear time, so the naive answer is the setup, not the solution.

This problem appears on the Blind 75 list and in LeetCode 75, in the bit manipulation section.

Examples

Constraints

• 0 <= n <= 100000

Note that n can be zero, so the answer is never an empty array. It always has at least the single entry for 0.

Which pattern this problem belongs to

This sits at the meeting point of bit manipulation and dynamic programming. The dynamic programming part is the one that matters: the answer for i is built from the answer for a smaller number you have already computed. Recognizing that is the whole difficulty, because the question looks like pure bit twiddling.

Approach

The key observation is that shifting a number right by one bit removes its lowest bit and leaves a smaller number you have already solved. So the count for i is the count for i >> 1, plus one if the lowest bit of i is set.

Written as a recurrence:

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

Both pieces are cheap. i >> 1 is always strictly less than i for i greater than zero, so the value on the right is already in the table when you need it. A single forward loop fills the array, which gives O(n) time with no extra space beyond the output.

A second recurrence solves it just as well and is worth knowing because interviewers sometimes ask for a different one. The expression i & (i - 1) clears the lowest set bit of i, so bits[i] = bits[i & (i - 1)] + 1. Both are linear. The shift version is easier to explain under pressure.

Python code

def count_bits(n):
    """bits[i] = bits[i >> 1] + (i & 1). O(n) time, O(1) extra space."""
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

def count_bits_clear_lowest(n):
    """The alternative recurrence: clearing the lowest set bit."""
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        bits[i] = bits[i & (i - 1)] + 1
    return bits

Java code

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;
}

Complexity

The output array itself is O(n), but it is the required answer rather than working memory, so it is conventional to exclude it.

Common mistakes

• Allocating n entries instead of n + 1. The array runs from 0 to n inclusive. This is the single most common bug on this question.
• Starting the loop at 0. Index 0 is already correct at zero, and 0 >> 1 is 0, so starting at 0 is harmless but pointless. Starting at 1 states the base case clearly.
• Reaching for the built-in bit count. Python offers bin(i).count("1") and Java offers Integer.bitCount. Using one answers the question but skips the reasoning the interviewer wants, so present the recurrence first and mention the built-in after.
• Mixing up the two recurrences. i >> 1 pairs with + (i & 1), and i & (i - 1) pairs with + 1. Crossing them gives wrong answers that look plausible on small inputs.

Related problems

• Number of 1 Bits, which is this question for a single number.
• Single Number, which uses exclusive or rather than counting.
• Reverse Bits, which manipulates the same representation in the opposite direction.

How to Prepare

• Say the recurrence out loud before coding. The implementation is four lines, so the interview is testing whether you can find the relationship, not whether you can write a loop.
• Practice reading numbers in binary. Writing 0 through 8 in binary by hand makes the shift relationship visible immediately.
• Work the pattern, not the problem. The dynamic programming families are laid out in Grokking the Coding Interview, and the most common LeetCode patterns is the short summary.