Counting Bits

How you get there

1. 1i >> 1 drops the lowest bit, and i & 1 recovers it.
2. 2So bits(i) = bits(i >> 1) + (i & 1).
3. 3Every value reuses an already-computed result, giving one pass.

Solution

def count_bits(n: int) -> list[int]:
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp

Time

O(n)

Space

O(n)

What goes wrong

Calling a popcount routine per value is correct but misses the linear DP the problem is testing.