Counting Bits
EasyBit manipulation
Count the 1 bits of every whole number from 0 to n, and return the counts as an array, the count for 0 first.
Aim for O(n) time, without counting each number’s bits from scratch.
Examples
Input: n = 6 Output: [0, 1, 1, 2, 1, 2, 2]
6 is 110 in binary, so the last entry is 2; 3 is 11, so its entry is 2 as well.
Input: n = 0 Output: [0]
Only the number 0, which has no 1 bits.
Constraints
0 ≤ n ≤ 10⁵
Stuck?
Hint 1
i >> 1 is i with its lowest bit dropped, and it is smaller than i, so its count is already in your array.
Hint 2
The count for i is the count for i >> 1, plus 1 if i is odd (i & 1).
The idea
Dropping the lowest bit of i gives i >> 1, half of i rounded down, a smaller number whose count is already known. So the count for i is the count for i >> 1, plus one if the dropped bit was a 1. Each entry then takes a single step.
Time O(n)Extra space O(1) besides the answer
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
0 has no 1 bits. It is the one count that does not come from a smaller number.
function countBits(n) { const answer = [0]; for (let i = 1; i <= n; i++) { answer.push(answer[i >> 1] + (i & 1)); } return answer;}The trap
Writing each number in binary and counting its 1s gives correct counts, only more slowly. The slip is the loop bound: i < n stops before n itself, so the array is one count short, and when n is 0 it comes back empty instead of holding a single 0.
function countBits(n) { const answer = []; for (let i = 0; i < n; i++) answer.push(i.toString(2).split('1').length - 1); // stops one short of n return answer;}