Counting Bits

Signal

"Bit count for every number up to n" is a giveaway that you shouldn't recompute each one from scratch (that's the number-of-1-bits approach repeated n times) — each count builds directly on a smaller already-computed count, which is a DP recurrence over bits.

Approach

Dropping the lowest bit of i (via i >> 1) gives a smaller number whose bit count you've already computed. The bit you dropped is exactly i & 1. So the bit count of i is the bit count of i >> 1 plus that dropped bit — fill the answer array left to right, each entry reusing an earlier one.

Skeleton

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

Solution

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

Complexity

O(n) time — one O(1) step per index, reusing prior work instead of recounting bits from scratch. O(n) space for the output array (required by the problem anyway).

Pitfalls

• Calling the number-of-1-bits routine independently for every index also works but is O(n log n) (or O(32n)) — the DP reuse is what makes this O(n), and that's usually the actual point of the follow-up.
• The recurrence depends on ans[i >> 1] already being filled — iterate indices in increasing order, not any other order, or the reused value won't exist yet.