LeetCode 338 ·
Easy
Counting Bits
Return the number of set bits for every integer from 0 to n.
Try it
Step through the core mechanic. The simulator below runs the bit manipulation shape this problem is built on.
Walk the pattern
No dedicated step-through for this one yet. The shape is Bit manipulation — its pattern page has the interactive walkthrough, the reference implementation, and a five-problem progression that this problem sits inside.
The approach
DP on bits: bits[i] = bits[i >> 1] + (i & 1) — drop the low bit (already counted) and add it back. Builds all n answers in O(n).
| Aspect | Value |
|---|---|
| Pattern | Bit manipulation |
| Recognise it by | Set-bit counts for 0..n via DP. |
| Time complexity | O(n) |
| Space complexity | O(n) |
| Difficulty | Easy |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.