Counting Bits Visualizer

i − offset offset = the highest power of two ≤ i · subtracting it drops exactly i's top 1 bit

dp dp[i] above i · the curve links dp[i] to the smaller entry it copies from

public int[] countBits(int n) { int[] dp = new int[n + 1]; int offset = 1; for (int i = 1; i <= n; i++) { if (offset * 2 == i) { // i is the next power of two offset = i; } dp[i] = 1 + dp[i - offset]; } return dp;}

i: —
offset: 1
dp[i − offset]: —
dp: —

Why it works

Brute force counts each number separately, clearing bits one at a time (Number of 1 Bits, 191; in Java, Integer.bitCount(i)). O(n log n) in total, and it ignores the counts already computed.
Drop the top bit: between two powers of two, offset ≤ i < 2·offset, so i is offset's single 1 bit plus the lower bits of i − offset. That gives dp[i] = 1 + dp[i − offset], and i − offset < i is already filled in.
One pass, O(1) work per entry: O(n) time. The answer list is the only storage, O(n), which the output needs anyway.
Pitfall: when to bump offset. It changes exactly when i reaches the next power of two (offset * 2 == i). At that moment i − offset = 0, so a power of two gets 1 + dp[0] = 1.
Other recurrences: dp[i] = dp[i >> 1] + (i & 1) drops the lowest bit instead, and dp[i] = dp[i & (i − 1)] + 1 clears the lowest 1. All three are O(n).