Counting Bits

Count each number — inspect every bit

Treat each integer as a separate popcount, the number of set bits in one value. Read its last binary digit with value & 1, add that digit to the count, then shift right until nothing remains.

def count_bits(n: int) -> list[int]:
    answer: list[int] = []
    for number in range(n + 1):
        value = number
        bits = 0
        while value > 0:
            bits += value & 1
            value >>= 1
        answer.append(bits)
    return answer

An integer up to n has O(log n) binary digits, and you repeat that work for all n + 1 integers. Time O(n log n). Space O(n) for the returned array, with O(1) extra working space.

Bit recurrence DP — reuse the smaller answer

Dynamic programming (DP) stores answers to smaller subproblems so a larger answer can reuse them. Shifting i right removes its last binary digit and produces a smaller index: i >> 1. The removed digit is exactly i & 1.

The transition is the rule that builds one DP answer from earlier answers. Here it is:

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

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

Every entry now takes constant work. The base case ans[0] = 0 is already in place, and every transition reads an earlier entry.

Time O(n). Space O(n) for the returned DP array, with O(1) extra working space.