FAANGPrep Sprint
Counting Bits
Given an integer n, return an array of the number of 1's for each number from 0 to n.
Examples
0 is 0, 1 is 1, 2 is 10 — so the counts are 0, 1 and 1.
5 is 101; shifted right it is 10, which is 2 with one bit, and the dropped digit is 1 — so dp[5] = 2.
Problem Understanding
We need to return an array ans of size n + 1 such that for each i, ans[i] counts the 1 bits when i is written in binary.
Example: n = 2
- 0 -> 0 (0)
- 1 -> 1 (1)
- 2 -> 10 (1)
- Output:
[0, 1, 1]
Algorithm Strategy
Counting the bits of one number costs O(log n), so doing it for all of them costs O(n log n). Dynamic programming makes it O(n).
The insight: i >> 1 is i with its last binary digit thrown away. It therefore has every bit of i except that one, and i & 1 is exactly the digit that was thrown away.
Recurrence: dp[i] = dp[i >> 1] + (i & 1)
Because i >> 1 is always smaller than i, the value it needs has already been written — so one forward pass is enough.
Interactive Visualization
ONE COLUMN PER NUMBER · THE CELL HOLDS ITS COUNT OF 1 BITS · OUTLINED = THE SHIFTED NUMBER IT REUSES
BASE CASE — dp[0] = 0
0
1
2
3
4
5
ones
n
5
filled
1/6
Answer
—
the shift
Pick a step inside the loop
The array starts as zeros, which already makes dp[0] = 0 — zero has no 1 bits
Next
Take i = 1, which is 1 in binary
n
n
Each column is one number and holds its count of 1 bits. Watch the outlined cell: it is always i >> 1, the same number with its last binary digit dropped — and the panel beside the figure lines the two up so you can see which digit went missing.
Try Past 8: every power of two drops the count straight back to 1.