Counting Bits

Given an integer n, count the number of 1's in the binary representation of every number in the range [0, n].

Return an array output where output[i] is the number of 1's in the binary representation of i.

0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100

Approach

Use DP: dp[i] = dp[i >> 1] + (i & 1). The number of set bits in i equals the number in i // 2, plus one if i is odd.

Why It Works

Right shifting removes the least significant bit. If that bit was 1, we add one; otherwise we add zero. This produces the correct count for each number in order.

Complexity

• Time: O(n)
• Space: O(n)

Reference Implementation (Python)

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