Given a non-negative integer n, for every number i from 0 to n, count the number of 1-bits in its binary representation. Return the result as an array.
For example, given n = 5, the output is [0, 1, 1, 2, 1, 2] because: 0=0, 1=1, 10=1, 11=2, 100=1, 101=2.
Explain how you would solve this in O(n) time (not O(n log n)). What pattern or recurrence can you exploit?
How to approach it
- Hint 1
Look at the relationship between a number and the number with its last bit removed. How do you remove the last bit?
- Hint 2
Right-shifting i by 1 gives i/2 (integer division). The bit count of i equals the bit count of i/2 plus whether i is odd.
- Hint 3
This gives the recurrence: bits[i] = bits[i >> 1] + (i & 1).
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.