Counting Bits
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
For every number from 0 to n return how many 1 bits it has.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What is 5 in binary, and what is 5 shifted right by one?
- Hint 2Fill the answers in increasing order so the half is already known.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
A number is its half with one extra bulb at the end: the last bulb is lit if the number is odd. So the lit-bulb count of 5 (101) equals the count of 2 (10) plus 1 because 5 is odd. Since you fill the list from 0 upward, the answer for the half is always already on your sheet.
- The obvious way
Count the bits of each number separately: O(n log n).
- The key insight
bits[0] = 0. For each i from 1 to n: bits[i] = bits[i shifted right by 1] + (i AND 1). One step each, O(n) total.
- The algorithm
- bits = [0].
- For each i: half = i shifted right.
- bits[i] = bits[half] + (1 if i is odd else 0).
- Return bits.
Watch it run
Examplen = 5
0 has no lit bulbs: 0.
0
Where people slip
- The answer array has n + 1 entries (0 through n).
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def count_bits(n):
bits = [0] * (n + 1)
for number in range(1, n + 1):
half = number >> 1 # drop the last bulb
bits[number] = bits[half] + (number & 1) # plus one if the last bulb is lit
return bitsNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.