LeetCode 338 Counting Bits - Solution

Use DP. The number of bits in i relates to previously computed values.

Key insight: i >> 1 (right shift) removes the last bit. i & 1 tells you if the last bit was 1.

So: bits[i] = bits[i >> 1] + (i & 1).

This is $O(1)$ per number using the already-computed bits[i >> 1].