Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Counting Bits

Problem (restated)

For each i in 0..n inclusive, return the number of 1-bits in binary representation of i.

Intuition

Right-shift drops LSB; add back (i & 1). Reuses smaller answers → O(n) total.

Approaches

DP: dp[i] = dp[i>>1] + (i&1)

Tested only

Time O(n)Space O(n)

Idea. Equivalent to dp[i] = dp[i & (i-1)] + 1 (popcount recurrence).

Walkthrough. n=5 → [0,1,1,2,1,2].

Trade-offs. Per-number Brian Kernighan is O(n log n) worst.

Solution

export function countBits(n: number): number[] {
  const dp = Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) dp[i] = dp[i >> 1]! + (i & 1);
  return dp;
}

export function countBits(n: number): number[] {
  const dp = Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) dp[i] = dp[i >> 1]! + (i & 1);
  return dp;
}

Template connection

Bit DP / popcount table.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?