285. Counting Bits
Given a non-negative integer n, build an array ans of length n + 1 where ans[i] is the number of 1 bits in the binary representation of i, for every i from 0 through n. Return the array.
For instance, 5 is 101 in binary, so its entry is 2.
Counting the bits of each number independently works — but every popcount from 0 to i - 1 is already sitting in your array. Can you fill the whole table in a single O(n) pass?
Example 1:
Input: n = 2
Output: [0, 1, 1]
Explanation: 0 → 0 (no bits set), 1 → 1 (one bit), 2 → 10 (one bit).
Example 2:
Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Explanation: The binary forms are 0, 1, 10, 11, 100, 101 — with 0, 1, 1, 2, 1, 2 set bits respectively.
Constraints:
- 0 ≤ n ≤ 10⁵
Hints:
The direct route: for each i, count its bits by repeatedly checking the low bit and shifting right. That is O(n log n) — already fast, but the problem is really asking for the recurrence hiding in the table.
Shifting i right by one bit drops its last binary digit: i >> 1 has either the same bit count as i (if i is even) or one fewer (if i is odd). And i >> 1 is smaller than i, so its answer is already computed.
That gives ans[i] = ans[i >> 1] + (i & 1). A sibling recurrence also works: ans[i] = ans[i & (i - 1)] + 1, since i & (i - 1) clears the lowest set bit.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 2
Expected output: [0, 1, 1]