Counting Bits
FreeBit manipulationEasy72 of 75
The problem
For every integer from 0 through n inclusive, return its number of set bits. Assume n ≥ 0.
Example
n = 5 → [0, 1, 1, 2, 1, 2]
Need a hint?
Removing the last binary digit gives an already computed number.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
Initialize counts[0] = 0. For i from 1 to n, set counts[i] = counts[i >> 1] + (i & 1). The shift removes the last bit, and the mask contributes one exactly when that bit was set.
Complexity
O(n) time and O(n) output space.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.