Counting Bits — Step-by-Step Visualization

Algorithm Pattern

Dynamic Programming (Bitwise)

Key Idea

The number of set bits in `i` is related to the number of set bits in `i >> 1` (which is `i/2`). Specifically, `bits[i] = bits[i >> 1] + (i & 1)`. The term `(i & 1)` is 1 if `i` is odd and 0 if `i` is even.

Step-by-Step Approach

1. Initialize an array `dp` of size `n + 1` with 0s.
2. Iterate `i` from 1 to `n`.
3. Calculate `dp[i] = dp[i >> 1] + (i % 2)`.
4. Return the `dp` array.

Common Gotchas

• Remember the base case `dp[0] = 0`.
• Bitwise shift `>> 1` is equivalent to integer division by 2.