Pattern visualizer
Counting Bits
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. Animated on: n = 5 — return an array where ans[i] is the number of 1 bits in i, for i = 0..n..
DP: reuse dp[i>>1], add the current bit
time O(n)space O(n)step 1 / 8
line 1
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