Problem Statement
Counting Bits
You are given a number n. Build an array that has one slot for every number from 0 up to n. In each slot, store how many 1's show up when you write that number in binary. Binary just means writing a number using only 0's and 1's, the way a computer sees it. So for the number 5, binary is 101, which has two 1's. The answer for slot 5 would be 2.
Signals to notice
Brute force first
For each number, count its bits individually. Each number is processed independently, ignoring the relationship between consecutive numbers. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
The key insight
dp[i] = dp[i >> 1] + (i & 1). Each number's bit count equals its right-shifted version's count plus its last bit. This works because right-shifting removes the last bit, and we already know the answer for the smaller number. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.
Trace it on n=5
init: dp = [0,0,0,0,0,0] (i=0 stays 0) i=1: dp[1>>1=0]+(1&1)=0+1=1 -> dp=[0,1,0,0,0,0] i=2: dp[2>>1=1]+(2&1)=1+0=1 -> dp=[0,1,1,0,0,0] i=3: dp[3>>1=1]+(3&1)=1+1=2 -> dp=[0,1,1,2,0,0] i=4: dp[4>>1=2]+(4&1)=1+0=1 -> dp=[0,1,1,2,1,0] i=5: dp[5>>1=2]+(5&1)=1+1=2 -> dp=[0,1,1,2,1,2] return [0,1,1,2,1,2]
What must stay true
Every number's bit count can be derived from a smaller number's bit count plus 0 or 1. The recurrence dp[i] = dp[i/2] + (i % 2) captures this — we never need to count bits from scratch. As long as that statement keeps holding, you can trust the steps built on top of it.
Shape of the loop
dp = array of zeros, size n+1
for i from 1 to n:
dp[i] = dp[i >> 1] + (i & 1) # count of i/2, plus i's last bit
return dpPseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not seeing the DP relationship — trying to count bits for each number independently. The key insight is that i >> 1 is always a number we've already computed. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.