TL;DR
DP that reuses a smaller already-counted number — O(n) time, O(1) extra space beyond the output array.
Approach 1 — Brute force: count every number
For each i from 0 to n, count its set bits independently.
def countBits(n: int) -> list[int]:
return [bin(i).count("1") for i in range(n + 1)]
Complexity: O(n log n) time — each of the n + 1 numbers costs O(log i) to scan its ~log n bits — O(1) extra space.
Why we can do better: this passes, but it ignores available structure. Each count reruns a full bit scan even though a smaller number with nearly the same bits was already counted.
Approach 2 — DP by dropping the lowest bit (i >> 1)
Shifting i right by one bit removes its lowest bit and leaves a strictly smaller number, i >> 1, whose count is already stored. The removed bit is i & 1. So the number of set bits in i is the count of i >> 1 plus that removed bit: one table lookup and one add.
def countBits(n: int) -> list[int]:
ans = [0] * (n + 1)
for i in range(1, n + 1):
ans[i] = ans[i >> 1] + (i & 1)
return ans
Walkthrough for n = 5:
| i | i >> 1 | ans[i >> 1] | i & 1 | ans[i] |
|---|
| 1 | 0 | 0 | 1 | 1 |
| 2 | 1 | 1 | 0 | 1 |
| 3 | 1 | 1 | 1 | 2 |
| 4 | 2 | 1 | 0 | 1 |
| 5 | 2 | 1 | 1 | 2 |
Result [0, 1, 1, 2, 1, 2]. Because i >> 1 < i, its entry is always filled before we need it. The dependency each ans[i] reads is a strictly smaller, already-computed index:
graph TD
A["ans[0] = 0"]
B["ans[1]"] --> A
C["ans[2]"] --> B
D["ans[3]"] --> B
E["ans[4]"] --> C
F["ans[5]"] --> C
Complexity: O(n) time, O(1) extra space (beyond the required output).
Approach 3 — DP by clearing the lowest set bit (i & (i - 1))
i & (i - 1) removes the lowest set bit of i. That leaves a smaller number with exactly one fewer 1, so ans[i] is that number’s count plus one. Where Approach 2 removed a positional bit (which might be 0), this removes an actual set bit.
Why does i & (i - 1) clear the lowest set bit? Subtracting 1 turns the lowest set bit into 0 and flips every zero below it to 1; ANDing with the original keeps all higher bits, kills that lowest set bit, and zeroes the flipped-up low bits.
def countBits(n: int) -> list[int]:
ans = [0] * (n + 1)
for i in range(1, n + 1):
ans[i] = ans[i & (i - 1)] + 1
return ans
Walkthrough for n = 5:
| i | binary | i & (i - 1) | ans[…] + 1 | ans[i] |
|---|
| 1 | 001 | 0 | 0 + 1 | 1 |
| 2 | 010 | 0 | 0 + 1 | 1 |
| 3 | 011 | 2 (010) | 1 + 1 | 2 |
| 4 | 100 | 0 | 0 + 1 | 1 |
| 5 | 101 | 4 (100) | 1 + 1 | 2 |
Result [0, 1, 1, 2, 1, 2].
Complexity: O(n) time, O(1) extra space.
Common pitfalls
- Array size off by one: the answer has
n + 1 entries (indices 0 through n), not n.
- Operator precedence: write
ans[i >> 1] + (i & 1) — & binds looser than +, so ans[i >> 1] + i & 1 would parse wrong. Keep the parentheses.
- Starting the loop at 0:
ans[0] is already 0; starting i at 1 avoids computing -1 in i & (i - 1).
- Reaching for a built-in:
bin(i).count("1") is fine for correctness but is the O(n log n) approach in disguise — not the intended O(n) DP.
Pattern takeaway
When a quantity over 0..n has a clean recurrence to a smaller value, build a table bottom-up instead of recomputing. For bit counts, the two go-to relations are “drop the lowest bit” (i >> 1, add i & 1) and “clear the lowest set bit” (i & (i - 1), add 1) — both turn an O(n log n) scan into an O(n) DP.