#338
Counting Bits
Easy Bits + DP
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
For every i from 0 to n, return how many 1-bits i has.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the number of 1-bits for every number from 0 to n.
Why this works: i >> 1 is i without its last bit, and we already know its answer. Add back the last bit with i & 1.
Example: n = 5
0:0 1:1 2:bits[1]+0=1 3:bits[1]+1=24:bits[2]+0=1 5:bits[2]+1=2[0, 1, 1, 2, 1, 2]
✦Hints open one at a time
The answer for i is related to the answer for i >> 1.
Shifting right drops the last bit; add it back with i & 1.
↗Approach
bits[i] = bits[i >> 1] + (i & 1). Each value reuses an already computed smaller value, so the whole array fills in O(n).
</>Solution (Java)
class Solution {
public int[] countBits(int n) {
int[] bits = new int[n + 1];
for (int i = 1; i <= n; i++) {
bits[i] = bits[i >> 1] + (i & 1); // half of i, plus the last bit
}
return bits;
}
}!Common mistake
Calling a popcount loop for every i — O(n log n). Fine, but the reuse trick is what interviewers look for.
Complexity
- Time: O(n).
- Space: O(n) for the output.
