Counting Bits

Counting the set bits of a single number takes O(log n) time, so counting them for every number from 0 to n independently costs O(n log n). The follow-up asks for O(n) — the way there is to notice that the answer for i can be built from an answer you already computed for a smaller number, which is exactly the 1-D DP pattern from problems like Climbing Stairs.

Popcount Every Number

Time O(n log n)Space O(1) extra

For each i from 0 to n, count its set bits from scratch using the n & (n-1) trick (clears the lowest set bit each iteration, one iteration per set bit).

class Solution:
    def countBits(self, n: int) -> list[int]:
        def popcount(x: int) -> int:
            count = 0
            while x:
                x &= x - 1
                count += 1
            return count
        return [popcount(i) for i in range(n + 1)]

Each call to popcount(i) costs up to O(log i) work, and this is repeated for all n + 1 numbers, giving O(n log n) time. No per-number result is reused, even though popcount(6) and popcount(3) are closely related (6 is just 3 shifted left by one bit).

1-D DP: Build from a Smaller Answer

OptimalTime O(n)Space O(n)

Every integer i relates to a smaller integer already in the table via a right shift: i >> 1 drops i’s lowest bit, and that dropped bit is exactly i & 1. So the number of set bits in i is the number of set bits in i >> 1, plus one more if i is odd:

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

This is a bottom-up DP exactly like Climbing Stairs’ dp[i] = dp[i-1] + dp[i-2] — each entry is computed in O(1) from an entry already filled earlier in the array (since i >> 1 < i for all i >= 1).

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

Stepping through n = 5: watch each new entry read the entry at i >> 1 — a smaller index already filled — and add only its lowest bit, i & 1.

dp table

How dp[i] is built from a smaller answer

i–

i >> 1–

i & 1–

dp[i]dp[0] =0base case

1 / 6

comparingresult

Base case: dp[0] = 0, since 0 has no set bits. Every later entry reads an already-filled entry to its left.

Correctness: dropping the lowest bit of i via i >> 1 always yields a smaller, already-computed index, and re-adding that bit’s contribution (i & 1) recovers the exact count for i.

Complexity: one pass, O(1) work per index using only already-filled table entries → O(n) time, matching the follow-up. The output array itself is O(n) space (unavoidable, since the array is the required output).

Popcount Every Number

1-D DP: Build from a Smaller Answer

More Bit Manipulation practice