DSA problem
Counting Bits
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.
A naive solution counts bits for each number independently, but the optimal approach uses dynamic programming in linear time. The recurrence ans[i] = ans[i >> 1] + (i & 1) observes that i shifted right by one bit drops the least significant bit; the number of set bits in that smaller value is already computed, and you simply add back 1 if the dropped bit was set.
Examples
Example 1
Input:
n = 2Output:
[0,1,1]Explanation: 0 is 0b0 (zero bits), 1 is 0b1 (one bit), 2 is 0b10 (one bit).
Example 2
Input:
n = 5Output:
[0,1,1,2,1,2]Explanation: 0->0, 1->1, 2->10, 3->11, 4->100, 5->101, with set-bit counts 0,1,1,2,1,2.
Example 3
Input:
n = 0Output:
[0]Explanation: Only the value 0 is in range, and it has zero set bits.
Constraints
- 0 <= n <= 10^5
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.