HARD Lab · Binary · 23

338. Counting Bits

Every number's bit count equals the bit count of its right-shifted half plus the lowest bit — a one-liner DP recurrence dp[i] = dp[i>>1] + (i&1) fills the entire answer array in a single O(n) pass.

● EasyDPBit ManipulationTypeScript

PROBLEM What we're solving

Given a non-negative integer n, return an array dp of length n+1 where dp[i] is the number of 1-bits in i. For n = 5: 0,1,2,3,4,5 in binary are 0,1,10,11,100,101, so the answer is [0,1,1,2,1,2].

KEY IDEA Strip the last bit — you already know the rest

Insight → shifting i right by one (i >> 1) drops the lowest bit. The result is a smaller index you've already computed. Add back that dropped bit (i & 1) and you have the full count: dp[i] = dp[i >> 1] + (i & 1). Every answer costs O(1) and depends on a previously-filled cell.

RECURRENCE Build the table in one pass

  • 0 · Base case. dp[0] = 0 — zero has no set bits.
  • 1 · Recurrence. For each i from 1 to n: dp[i] = dp[i >> 1] + (i & 1). Right-shifting halves the index (already filled); the low bit tells us if that last bit was a 1.
  • 2 · Return. dp is complete. No second pass needed.
Classic confusion → many learners reach for i & (i - 1) (Brian Kernighan — clears the lowest set bit) which also works: dp[i] = dp[i & (i - 1)] + 1. Both recurrences are O(n) overall, but i >> 1 is slightly cleaner because it only uses ordinary array indexing; the Kernighan form looks cleverer but is harder to read at a glance. Know both; default to the shift.

COST Complexity & alternatives

Naive — popcount each i
O(n log n)
Each popcount is O(log i) bit operations.
DP recurrence
O(n)
O(n) time; O(n) space for the output array (unavoidable).

Two equivalent recurrences

dp[i] = dp[i >> 1] + (i & 1) (shift) and dp[i] = dp[i & (i - 1)] + 1 (Kernighan) both reduce to previously-known values in O(1). The shift form is the idiomatic choice for this problem.

Pattern transfer → the "reuse a smaller sub-problem" trick appears in Number of 1 Bits (popcount a single value), Power of Two (n & (n-1) === 0), Sum of Two Integers (bit-level addition), and any DP where the transition discards one element of the representation.

RUN IT Build dp[0..n] via the half-index recurrence

step 0 / 11
STARTBuild dp[0..5] where dp[i] = number of 1-bits in i. Base case: dp[0] = 0.
dp[ ]00?1?2?3?4?5
State
—
i
—
i >> 1
—
i & 1
—
dp[i]
dp[i] being computeddp[i>>1] — the source halffully filled array
slowfast

TYPESCRIPT The solution, annotated

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

Reading it block by block

Line 2 — allocate the result. A length-(n+1) array pre-filled with 0 gives us the base case dp[0] = 0 for free and avoids separate bounds checks.
Lines 3–5 — the recurrence loop. For each i from 1 to n: i >> 1 is the index of the same number with its lowest bit removed — always less than i, so already computed. i & 1 is 1 when the lowest bit is set, 0 otherwise. Summing them gives the full popcount.
Line 6 — return. The array is complete after one forward pass. No sorting, no repeated bit-twiddling loops — each answer is a single addition.
Complexity → O(n) time (one pass, O(1) work per element), O(n) space for the output array — which is the required output, so no extra space is used beyond what the problem demands.

INTERVIEWFollow-ups they'll ask

  • "Can you do it without the DP array, just for a single number?" Yes — n & (n - 1)clears the lowest set bit; loop until zero, counting iterations. That's O(k) for k set bits.
  • "Why is the naive O(n log n)?" Counting bits of each number i takes O(log i) operations; summing log 1 + log 2 + … + log n ≈ n log n.
  • "Give the alternative recurrence." dp[i] = dp[i & (i - 1)] + 1 — Brian Kernighan: each step clears the lowest set bit, which is a previously-computed index.
  • "What if n could be very large and memory matters?" The problem requires the full output array, so O(n) space is mandatory. For a single query use the bit-loop or the hardware popcount instruction.
  • "Edge cases?" n = 0 → [0]. The loop body never executes and the pre-filled array is the answer.

MNEMONIC The one-liner

"Chop the last bit, look up the half, add that bit back."

TRIGGERS When you see ___ → reach for ___

"return array of bit counts for 0..n"DP with dp[i>>1] + (i&1)
popcount of every number up to none-pass DP, reuse smaller index
i & 1 — check lowest bitisolate LSB, value is 0 or 1
i >> 1 — drop lowest bitparent index in the DP table

SKELETON The reusable shape

skeleton.ts
const dp: number[] = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
  dp[i] = dp[i >> 1] + (i & 1);
}
return dp;

FLASHCARDS Tap to flip

What does dp[i] mean?
The number of 1-bits (popcount) of i.
tap to flip
1 / 7
Answer to reveal explanations. No penalty for retries.Score: 0 / 7
QUESTION 01
What is the recurrence used to fill dp[i]?
QUESTION 02
Trace the algorithm: what is dp[6] when n = 6?
QUESTION 03
Time complexity of the DP solution?
QUESTION 04
Why is i >> 1 always a valid (already-filled) index?
QUESTION 05
The alternative recurrence dp[i] = dp[i & (i - 1)] + 1 is based on:
QUESTION 06
What does countBits(0) return?
QUESTION 07
For n = 5, the full output is [0,1,1,2,1,2]. Which value is wrong in [0,1,1,2,2,2]?