Counting Bits
Counting Bits is an easy Bit Manipulation problem from the Blind 75. The key pattern is dp on bits, and a good solution runs in O(n) time.
Problem
For every integer from zero through n, return its number of set bits.
Examples
Example 1
Input
5Output
[0,1,1,2,1,2]Example 2
Input
4Output
[0,1,1,2,1]Example 3
Input
7Output
[0,1,1,2,1,2,2,3]Approach
The bit count of i equals the count of i >> 1 plus its lowest bit, so fill the answers in increasing order.
| Pattern | DP on bits |
|---|---|
| Time | O(n) |
| Space | O(1) beyond the output |
Watch out for
The output has n + 1 entries, from 0 to n.