Counting Bits
DP: reuse dp[i>>1], add the current bit
time O(n)space O(n)
Every number i is either double some smaller number j (i even, same bit count as j) or one more than double j (i odd, one extra bit). Shifting i right by 1 gives that j directly, so dp[i] = dp[i >> 1] + (i & 1) builds the whole table in one pass with no bit-counting per number.
Details
Animated on: n = 5 — return an array where ans[i] is the number of 1 bits in i, for i = 0..n.
Problem:Counting BitsEasy
Pattern:Bit Manipulation
DP: reuse dp[i>>1], add the current bit
step 1 / 8
Build dp bottom-up: dp[i] = dp[i>>1] + (i&1) reuses the popcount of a smaller number already computed.
Pseudocode
1FUNCTION countBits(n):2 dp = a list starting with [0]3 FOR i from 1 to n:4 (reuse the bit count of i halved, then add i's lowest bit)5 dp[i] = dp[i halved, rounded down] + (i's lowest bit: 1 if odd, else 0)6 RETURN dp
← / → step · space play · Home restart
Every step in words
Show all 8 steps
- Build dp bottom-up: dp[i] = dp[i>>1] + (i&1) reuses the popcount of a smaller number already computed.
- dp[0] = 0 — the base case, zero has no set bits.
- dp[1] = dp[1>>1] + (1&1) = dp[0] + 1 = 0 + 1 = 1.
- dp[2] = dp[2>>1] + (2&1) = dp[1] + 0 = 1 + 0 = 1.
- dp[3] = dp[3>>1] + (3&1) = dp[1] + 1 = 1 + 1 = 2.
- dp[4] = dp[4>>1] + (4&1) = dp[2] + 0 = 1 + 0 = 1.
- dp[5] = dp[5>>1] + (5&1) = dp[2] + 1 = 1 + 1 = 2.
- dp = [0,1,1,2,1,2] — the full popcount table for 0..5. Return dp.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.