Counting Bits

Given a non-negative integer n, return an array answer where answer[i] is the number of 1 bits in the binary representation of i for every 0 <= i <= n.

Input / output

• Input: n: int
• Output: int[] of length n + 1

Examples

1. n = 2 returns [0,1,1]. 0 has zero set bits, 1 has one, and 2 (10 in binary) also has one.
2. n = 5 returns [0,1,1,2,1,2]. 3 is 11 and 5 is 101, so both contribute two set bits.
3. n = 0 returns [0]. The range still includes zero itself.

Constraints

• 0 <= n <= 10^5

Edge cases

• n can be zero.
• The answer must include every value from 0 through n in order.

Target complexity

• Aim for O(n) time and O(n) output space.

Hints

1. i >> 1 drops the least significant bit of i.
2. The bit count of i equals the bit count of i >> 1 plus the final bit i & 1.

Follow-up Can you derive the same recurrence using i & (i - 1) instead?