Counting Bits

We need to return an array ans of size n + 1 such that for each i, ans[i] is the number of 1's in the binary representation of i.

Example: n = 2

• 0 -> 0 (0)
• 1 -> 1 (1)
• 2 -> 10 (1)
• Output: [0, 1, 1]

Instead of counting bits for each number individually (O(N log N)), we can use DP (O(N)).

Key Insight:

• i (even): number_of_ones(i) == number_of_ones(i / 2) (shifting left adds a 0, count doesn't change).
• i (odd): number_of_ones(i) == number_of_ones(i / 2) + 1 (last bit is 1).

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

Watch how dp[i] reuses the result from dp[i >> 1]. The pointers show the dependency.

Try clicking 'Randomize' to test different n.