Counting Bits

This problem sits between bit manipulation and dynamic programming. The bit part is small; the real idea is that every number is one shift away from a smaller number whose answer you already have. Interviewers like it because the brute force is obvious, and the "O(n) in a single pass without built-ins" requirement forces you to find that reuse.

The problem

Given an integer n, return a list ans of length n + 1 where ans[i] is the number of 1 bits in i, for every i from 0 to n.

Example 1. n = 5 → [0, 1, 1, 2, 1, 2]. In binary, 0 to 5 are 0, 1, 10, 11, 100, 101.

Example 2. n = 8 → [0, 1, 1, 2, 1, 2, 2, 3, 1]. 7 is 111 (three 1s) and 8 is 1000 (one).

Constraints. 0 ≤ n ≤ 10⁵. The follow-up asks for O(n) time without a built-in bit counter.

Clarifying questions

• Include 0? Yes, the list has n + 1 entries, starting with ans[0] = 0.
• Can I use bin(i).count("1")? For the first version, yes. The follow-up says no.
• Is memory a concern? The output is O(n) anyway; aim for no more than that.

Approach 1: the simple way

Count the bits of each number on its own, using Number of 1 Bits.

1def count_bits_brute(n: int) -> list[int]:2    """Count each number's bits separately."""3    result = []4    for i in range(n + 1):5        count, x = 0, i6        while x:7            x &= x - 1          # clear one set bit8            count += 19        result.append(count)10    return result

Each number i has at most log₂(i) + 1 bits, so the total is O(n log n). At n = 10⁵ that is about 815,000 inner steps (one per 1 bit, counted by running it) — not slow in absolute terms. But it ignores the requirement, and it throws away information: to count the bits of 6, it starts from nothing, even though it just finished counting the bits of 3, and 6 is simply 3 shifted left.

The key insight

Look at any number in binary and chop off its last bit. What is left is i >> 1, which is i // 2 — a smaller number. Its count is already in the list, because we fill the list in order.

So the count for i is the count for i >> 1, plus 1 if the chopped-off bit was a 1. That last bit is i & 1.

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

Take 6 = 110. Chop off the last bit: 11 = 3, which has 2 ones. The chopped bit is 0. So 6 has 2 ones. Take 7 = 111. Chop: 11 = 3, 2 ones, and the chopped bit is 1, so 7 has 3. Each answer costs one lookup and one addition.

This is dynamic programming in its simplest form: the answer for a bigger input is built from the answer for a smaller one.

Approach 2: one pass with i >> 1

1def count_bits(n: int) -> list[int]:2    """dp[i] = dp[i >> 1] + (i & 1): reuse the answer for i without its last bit."""3    dp = [0] * (n + 1)4    for i in range(1, n + 1):5        dp[i] = dp[i >> 1] + (i & 1)6    return dp

Step by step:

1. dp[0] = 0: zero has no 1 bits.
2. For each i from 1 upward, i >> 1 is smaller than i, so dp[i >> 1] is already filled.
3. Add the last bit, i & 1.

Dry run for n = 8:

The result is [0, 1, 1, 2, 1, 2, 2, 3, 1], matching Example 2.

Complexity. O(n) time: one lookup, one shift and one addition per number. O(n) space for the output, and nothing more.

Approach 3: the same idea with i & (i - 1)

There is a second recurrence, using the trick from Number of 1 Bits. i & (i - 1) is i with its lowest 1 bit removed. That number is smaller, so its count is known, and it has exactly one fewer 1 bit:

1def count_bits_lowbit(n: int) -> list[int]:2    """dp[i] = dp[i & (i - 1)] + 1: i has one more 1 bit than i without its lowest one."""3    dp = [0] * (n + 1)4    for i in range(1, n + 1):5        dp[i] = dp[i & (i - 1)] + 16    return dp

For i = 6 = 110: 6 & 5 = 100 = 4, which has 1 bit, so 6 has 2. Same complexity, same result. Present whichever you derived; knowing both shows you understand why they work.

Measured in Python for n = 10⁶: the i >> 1 loop took 0.05 seconds, the per-number Kernighan loop 0.37 seconds, and [bin(i).count("1") for i in range(n + 1)] 0.09 seconds — the built-in string trick is fast because it runs in C. The O(n) recurrence still wins, and it is the one the follow-up asks for.

Edge cases

• n = 0. The loop does not run; the answer is [0].
• Powers of two. 1, 2, 4, 8 all have count 1. With i >> 1, each looks up the previous power of two and adds 0.
• Numbers just below a power of two (7, 15, 31). All 1s. Each looks up the previous all-ones number and adds 1.

Follow-ups

• "Return the total number of 1 bits from 0 to n." Sum the list, or compute it directly: each bit position repeats a pattern of 2ᵏ zeros then 2ᵏ ones, so it can be counted per position in O(log n).
• "Which numbers from 0 to n have exactly k bits set?" Filter the dp list. For the count alone, combinatorics on the binary digits of n gives O(log n).
• "Why is this dynamic programming?" Each answer is built from a smaller subproblem's answer, and the subproblems are solved in increasing order so each lookup is ready — exactly the tabulation pattern from the dynamic programming section.