The problem
For every number from 0 to n, count the 1 bits in its binary form. Return the list of counts.
Input: n = 8 Output: [0, 1, 1, 2, 1, 2, 2, 3, 1]
Picture it
Picture each number as a switch panel. Shifting a number right by one (halving it) just drops its last switch. So the count for i = the count for i ÷ 2 (already computed) + the last switch (i is odd → 1).
How to recognise it
- You need an answer for every number from 0 to n, not just one.
- The answer for i can be built from the answer for a smaller number you have already computed: that is dynamic programming (DP: store answers to small cases and reuse them).
- Shifting right by one (
i >> 1, the same asi // 2) drops the last bit, so i and i // 2 share all bits except one. - n is up to 10^5, and the follow-up asks for O(n) time with no built-in popcount.
Start with brute force
Count the 1 bits of each number separately, one bit at a time.
def count_bits_brute(n):
ans = []
for i in range(n + 1):
c, x = 0, i
while x:
c += x & 1
x >>= 1
ans.append(c)
return ans
Each number takes as many steps as it has bits, about log2(i), so the total is O(n log n): roughly 1.7 × 10^6 steps for n = 10^5. That passes, but it ignores that every number repeats the work already done for a smaller one.
From brute force to the idea
- Find the waste. Counting the bits of 13 (1101) re-counts the bits of 6 (110), which was finished seven numbers earlier.
- Split off the last bit.
i >> 1is i without its last bit, andi & 1is that last bit (1 if i is odd). So the 1 bits of i are the 1 bits ofi >> 1plusi & 1. - Fill the table in order.
i >> 1is smaller than i for every i ≥ 1, soans[i >> 1]is always ready when i is reached. - Start from the base case.
ans[0] = 0, already set by[0] * (n + 1).
This is the key idea: ans[i] = ans[i >> 1] + (i & 1), one O(1) step per number.
Another valid recurrence is ans[i] = ans[i & (i - 1)] + 1, which uses the "clear the lowest 1 bit" trick from Number of 1 Bits.
The key idea
bits[i] = bits[i >> 1] + (i & 1). O(n).
Python solution
def count_bits(n):
ans = [0] * (n + 1)
for i in range(1, n + 1):
ans[i] = ans[i >> 1] + (i & 1) # i = (i // 2) shifted, plus last bit
return ansIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force (count each) | O(n log n): about log2(i) steps per number | O(1) besides the output |
DP on i >> 1 (shown code) | O(n): one lookup and one addition per number | O(1) besides the output list of n + 1 counts |
Edge cases
- n = 0: returns
[0]; the loop never runs. - Powers of two (1, 2, 4, 8): each has count 1, because
i >> 1is the previous power of two andi & 1is 0. - All ones (7 = 111):
ans[3] + 1= 3. - n = 10^5: a list of 100,001 small integers, no problem.
Common mistakes
- Writing
ans[i >> 1] + 1, which forgets that the dropped bit may be 0: 2 (binary 10) then gets 2 instead of 1. - Writing
ans[i] = ans[i - 1] + 1, which only holds when i − 1 is even. - Starting the loop at 0 and computing
ans[0]fromans[0]: harmless here, but a sign of not thinking about the base case. - Precedence:
ans[i >> 1] + i & 1means(ans[i >> 1] + i) & 1; keep the brackets aroundi & 1.
Return, for each i from 0 to n, 1 if i has an odd number of 1 bits and 0 if even. For n = 8 the answer is [0, 1, 1, 0, 1, 0, 0, 1, 1]. Do it in O(n). Describe your approach, then write it if you like.
Compare with our answer
Same split: the parity of i is the parity of i >> 1, flipped if the last bit is 1. Flipping a 0/1 value is XOR with 1, so XOR replaces the addition.
def parity_bits(n):
ans = [0] * (n + 1)
for i in range(1, n + 1):
ans[i] = ans[i >> 1] ^ (i & 1)
return ans
Time O(n), and the output takes O(n) space.
A strong answer mentions: reusing ans[i >> 1], that adding a bit and keeping only odd/even is XOR, and the base case ans[0] = 0.
1. You must output, for every i from 0 to n, the position of its highest 1 bit (0 for i = 1). Which approach fits best?
Shifting right moves the highest bit down one position, so the position grows by exactly 1 from i >> 1 to i. The previous number usually has the same highest bit, and the other two count bits, not positions.
2. Why is ans[i >> 1] always available when the loop reaches i?
The loop goes upwards, and halving makes the index strictly smaller for every i ≥ 1, so that entry was computed earlier. i >> 1 can be odd (for example, 7 >> 1 is 3).
3. A learner writes ans[i] = ans[i >> 1] + 1. What is the first value of i where the list is wrong?
For i = 2 (binary 10), the shift drops a 0 bit, but the code still adds 1, giving 2 instead of 1. For i = 1, ans[0] + 1 is 1, which is correct.
Score 60% or more and the lesson is marked complete.