LeetCode 338 Counting Bits - Problem Statement

Return an array where ans[i] is the number of 1 bits in the binary representation of i, for all $0 \le i \le n$.

With n = 2:

• 0 = 0 (binary). 0 ones.
• 1 = 1. 1 one.
• 2 = 10. 1 one.
• Answer: [0, 1, 1].

With n = 5:

• 0→0, 1→1, 2→1, 3→2, 4→1, 5→2.
• Answer: [0, 1, 1, 2, 1, 2].

Solve in $O(n)$ time without using the built-in popcount function for each number.

Constraints: $0 \le n \le 10^5$.