Loading…

easyBit ManipulationLC #338Sometimes asked

Counting Bits

Q: How do you solve Counting Bits using the Per-Number Popcount (Brian Kernighan) approach?

When to use it: Open with this: 'I can count each number's bits independently — here's the O(n log n) version' — then improve it. Solve every index independently: for each `i` from `0` to `n`, count its set bits with Brian Kernighan's `i & (i - 1)` loop and store that in `ans[i]`. **Why this is the honest starting point.** It composes a tool we already trust (single-number popcount) over a range. There's no insight required — it's a loop wrapped around a loop — which is exactly why it's the right thing to state first before optimising. **Why it's O(n log n) and not O(n).** Each number takes time proportional to its number of set bits, which is at most `log i + 1`. Adding that up over `0..n` gives roughly `n log n` total operations. The follow-up explicitly asks you to remove that `log` factor, which is the cue to look for shared structure between consecutive numbers. **Why we don't ship it.** It's correct and passes, but it throws away an obvious relationship: the bit count of `i` is almost the bit count of a smaller number we *just computed*. Recomputing from scratch each time is the waste the DP eliminates. Time complexity: O(n log n). Space complexity: O(1).

Q: How do you solve Counting Bits using the DP — Reuse the Right-Shifted Result (Optimal) approach?

When to use it: The answer the follow-up wants. Say 'bits(i) = bits(i >> 1) + (i & 1): chop the last bit, look up the smaller number, add the bit back'. Fill the answer array left to right. For each `i`, look up the already-computed count for `i >> 1` and add the lowest bit `i & 1`. **Why `i >> 1` is the subproblem.** Right-shifting by one deletes the lowest bit of `i` — it's `i` with its last binary digit chopped off. Crucially `i >> 1 > 1]`. The number `i` therefore inherits every set bit of `i >> 1`. **Why we add `i & 1`.** The only bit `i >> 1` doesn't account for is the one we chopped off — the lowest bit of `i`. That bit is `1` when `i` is odd and `0` when even, which is exactly `i & 1`. So the full count is `bits(i >> 1) + (i & 1)`. Concretely, `6 = 110` shifts to `3 = 11` (two set bits) and `6 & 1 = 0`, giving `2`; `7 = 111` shifts to the same `3 = 11` but `7 & 1 = 1`, giving `3`. **Why the base case is `dp[0] = 0`.** Zero has no set bits, and every recurrence eventually bottoms out at it (repeated halving reaches `0`). Initialising the array to zeros gives this for free, so the loop can start at `i = 1`. **An equivalent recurrence worth naming.** `dp[i] = dp[i & (i - 1)] + 1`: `i & (i - 1)` clears the lowest *set* bit, producing a smaller solved number, and we add `1` for the bit we cleared. Either recurrence is O(1) per element — mention both to show range. Time complexity: O(n). Space complexity: O(1).

LCPractice

Bit Manipulation · 3 of 20 · 7 min

Given an integer n, return an array ans of length n + 1 such that for each i (0 ≤ i ≤ n), ans[i] is the number of 1's in the binary representation of i.

Follow-up: it is very easy to come up with a solution with O(n log n) time. Can you do it in linear time O(n) and possibly in a single pass? Can you do it without any built-in function like __builtin_popcount?

In plain English

Produce the set-bit count for every integer from 0 up to n, all at once. The interesting part is the follow-up: instead of counting each number from scratch, build each answer from a smaller one you've already computed.

Examples

Example 1

Input: n = 2
Output: [0, 1, 1]
Note: 0 → 0 bits, 1 → 1 bit, 2 (10) → 1 bit.

Example 2

Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Note: 0→0, 1→1, 2(10)→1, 3(11)→2, 4(100)→1, 5(101)→2.

Example 3

Input: n = 0
Output: [0]
Note: Only index 0, which has zero set bits.

Constraints

0 ≤ n ≤ 10⁵
ans.length == n + 1
ans[0] is always 0
Follow-up target: O(n) time, no popcount builtins

Clarifying questions4First question: Should the output include index 0?Explore questions

Q1.Should the output include index 0?
Yes — the array has length n + 1, covering 0..n inclusive, and ans[0] = 0.
Q2.Is n guaranteed non-negative?
Yes, 0 ≤ n ≤ 10⁵, so I don't need to worry about negative indices or the sign bit.
Q3.Does the output array count against my space complexity?
It's the required output, so it doesn't count as extra space. The DP uses only O(1) auxiliary space beyond the array.
Q4.Can I use a language builtin like Integer.bitCount in a loop?
That gives the O(n log n)... actually O(n) with hardware popcount, but the follow-up wants me to show the DP recurrence, so I'll implement it manually.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Return an array where ans[i] is the number of set bits in i, for all i from 0 to n. The naive answer popcounts each number independently in O(n log n). The optimal answer reuses earlier results: dp[i] = dp[i >> 1] + (i & 1), giving O(n) time and O(1) extra work per number.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can spot the overlapping subproblem hiding in the binary representation — that bits(i) relates to bits(i/2) — and turn an O(n log n) popcount loop into an O(n) DP.

Where candidates slip

Stopping at the per-number popcount (correct but O(n log n)), or deriving a recurrence but mis-handling the base case dp[0] = 0 or the odd-bit correction.

How to stand out

Derive the recurrence from the binary structure out loud (right-shift removes the lowest bit; i & 1 restores it), mention the alternative dp[i & (i-1)] + 1, and state extra space is O(1) since the array is the required output.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Per-Number Popcount (Brian Kernighan)	`O(n log n)`	`O(1)`	Open with this: 'I can count each number's bits independently — here's the O(n log n) version' — then improve it.	Read
2	DP — Reuse the Right-Shifted Result (Optimal)Optimal	`O(n)`	`O(1)`	The answer the follow-up wants. Say 'bits(i) = bits(i >> 1) + (i & 1): chop the last bit, look up the smaller number, add the bit back'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewCount bits for every i in 0..nCount each number independently?YesNo, reuseExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Per-Number Popcount (Brian Kernighan)

TimeO(n log n)SpaceO(1)

Open with this: 'I can count each number's bits independently — here's the O(n log n) version' — then improve it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You already know how to count the set bits of one number. What if you just do that for every i from 0 to n?

2Hint 2Explore hint

For each i, run Brian Kernighan's n & (n - 1) loop to count its bits and store the result at ans[i].

3Hint 3Explore hint

Each number costs O(number of set bits) ≤ O(log i), and there are n numbers → O(n log n) overall.

A · Core idea

Solve every index independently: for each i from 0 to n, count its set bits with Brian Kernighan's i & (i - 1) loop and store that in ans[i].

Why this is the honest starting point. It composes a tool we already trust (single-number popcount) over a range. There's no insight required — it's a loop wrapped around a loop — which is exactly why it's the right thing to state first before optimising.

Why it's O(n log n) and not O(n). Each number takes time proportional to its number of set bits, which is at most log i + 1. Adding that up over 0..n gives roughly n log n total operations. The follow-up explicitly asks you to remove that log factor, which is the cue to look for shared structure between consecutive numbers.

Why we don't ship it. It's correct and passes, but it throws away an obvious relationship: the bit count of i is almost the bit count of a smaller number we just computed. Recomputing from scratch each time is the waste the DP eliminates.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 5

i=0

0 has no set bits

Stateans = [0]

Final result[0, 1, 1, 2, 1, 2]

C · Code with teaching comments

Reference implementation previewpublic int[] countBits(int n) { int[] ans = new int[n + 1]; for (int i = 0; i <= n; i++) { int x = i, count = 0; while (x != 0) {Explore the full code

solution.javaJava

Per-Number Popcount (Brian Kernighan) — reference

3 teaching notes

1
public int[] countBits(int n) {
2
    int[] ans = new int[n + 1];
3
    for (int i = 0; i <= n; i++) {
4
        // Copy i so we can destroy x while counting, keeping i for the index.
5
        int x = i, count = 0;
6
        // Kernighan loop — once per set bit of this number.
7
        while (x != 0) {
8
            x &= (x - 1);
9
            count++;
10
        }
11
        // Store this number's popcount, computed from scratch.
12
        ans[i] = count;
13
    }
14
    return ans;
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n log n) timeO(1) spaceOpen the invariant and proofExplore the proof

Doing independent work per number is the classic 'no memoisation' smell. The moment you notice consecutive numbers share most of their bits, you should suspect a recurrence — that's the jump to the DP.

ComplexityO(n log n) time, O(1) space — For each of the n + 1 numbers we run a popcount loop that costs up to O(log i) (number of set bits). Summed across the range that's O(n log n) time; only the output array, no extra space.

E · Edge cases and pitfalls5n = 0 — Loop runs once for i = 0; inner while never executes → ans = [0].Explore edge cases

Edge cases handled

n = 0Loop runs once for i = 0; inner while never executes → ans = [0].
n = 1ans[0] = 0, ans[1] = 1 → [0, 1].

Pitfalls

Mutating i directly instead of a copy — you'd lose the loop index.
Calling a builtin popcount and claiming O(n) — true with hardware popcount, but it dodges the follow-up's intent to show a recurrence.
Off-by-one on the array size — it must be n + 1, not n.

03.2

Approach 2 of 2 · Optimal

DP — Reuse the Right-Shifted Result (Optimal)

TimeO(n)SpaceO(1)

The answer the follow-up wants. Say 'bits(i) = bits(i >> 1) + (i & 1): chop the last bit, look up the smaller number, add the bit back'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

How does the binary form of i relate to the binary form of i / 2 (i.e. i >> 1)?

2Hint 2Explore hint

i >> 1 is i with its lowest bit removed. So i has all the set bits of i >> 1, plus possibly the one bit you removed.

3Hint 3Explore hint

That removed bit is exactly i & 1. So dp[i] = dp[i >> 1] + (i & 1), and i >> 1 < i means it's already computed.

A · Core idea

Fill the answer array left to right. For each i, look up the already-computed count for i >> 1 and add the lowest bit i & 1.

Why `i >> 1` is the subproblem. Right-shifting by one deletes the lowest bit of i — it's i with its last binary digit chopped off. Crucially i >> 1 < i, so by the time we reach i we have already filled dp[i >> 1]. The number i therefore inherits every set bit of i >> 1.

Why we add `i & 1`. The only bit i >> 1 doesn't account for is the one we chopped off — the lowest bit of i. That bit is 1 when i is odd and 0 when even, which is exactly i & 1. So the full count is bits(i >> 1) + (i & 1). Concretely, 6 = 110 shifts to 3 = 11 (two set bits) and 6 & 1 = 0, giving 2; 7 = 111 shifts to the same 3 = 11 but 7 & 1 = 1, giving 3.

Why the base case is `dp[0] = 0`. Zero has no set bits, and every recurrence eventually bottoms out at it (repeated halving reaches 0). Initialising the array to zeros gives this for free, so the loop can start at i = 1.

An equivalent recurrence worth naming. dp[i] = dp[i & (i - 1)] + 1: i & (i - 1) clears the lowest set bit, producing a smaller solved number, and we add 1 for the bit we cleared. Either recurrence is O(1) per element — mention both to show range.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 5

Interactive diagram

Each number reuses its right-shifted self

i=1

Active call / nodeSupporting contextReturned stateNot active

dp[i] points back to dp[i >> 1], a smaller index already solved; the label adds (i & 1).

Final result[0, 1, 1, 2, 1, 2]

C · Code with teaching comments

solution.javaJava

DP — Reuse the Right-Shifted Result (Optimal) — optimal

3 teaching notes

1
public int[] countBits(int n) {
2
    // Initialised to all zeros — gives dp[0] = 0 for free, the base case.
3
    int[] dp = new int[n + 1];
4
    // Start at 1 since dp[0] is already correct.
5
    for (int i = 1; i <= n; i++) {
6
        // Bits of i = bits of i with last digit chopped (i >> 1) plus that last bit (i
7
        // & 1).
8
        dp[i] = dp[i >> 1] + (i & 1);
9
    }
10
    return dp;
11
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.11 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

The whole speedup comes from noticing that binary numbers nest: every number is a smaller number with one extra bit on the end. Once you see bit count as 'count of the prefix + the last bit', the O(n) DP writes itself. This 'derive the big case from a structurally smaller, already-solved case' move is the essence of DP.

ComplexityO(n) time, O(1) space — Each index does O(1) work — one array lookup, one shift, one AND, one add. Across n + 1 indices that's O(n) time; the only storage is the required output array, so O(1) extra space.

E · Edge cases and pitfalls5n = 0 — Loop body never runs; dp stays [0]. The zero-initialised array is already the answer.Explore edge cases

Edge cases handled

n = 0Loop body never runs; dp stays [0]. The zero-initialised array is already the answer.
n = 8dp[8] = dp[4] + 0 = 1 (8 = 1000). Powers of two correctly resolve to a single set bit via the chain 8→4→2→1.

Pitfalls

Forgetting dp[0] = 0 base case — though zero-initialising the array handles it implicitly.
Writing dp[i] = dp[i >> 1] + 1 unconditionally — you must add (i & 1), which is 0 for even i.
Using the recurrence with i decreasing or referencing a not-yet-filled index — always shift toward smaller, already-computed indices.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int[] countBits(int n) { int[] dp = new int[n + 1]; for (int i = 1; i <= n; i++) { dp[i] = dp[i >> 1] + (i & 1); }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Adding 1 instead of (i & 1)

Only odd numbers gain a set bit over their right-shifted half. Adding 1 for even i overcounts every even index.

Explore the code comparison

Don't write this

for i in range(1, n + 1):
    dp[i] = dp[i >> 1] + 1   # wrong: even i adds a phantom bit

Write this instead

for i in range(1, n + 1):
    dp[i] = dp[i >> 1] + (i & 1)   # add the actual lowest bit

Off-by-one array size

The output must cover 0..n inclusive — that's n + 1 entries. Sizing it n drops the answer for i = n.

Explore the code comparison

Don't write this

int[] dp = new int[n];        // missing index n
for (int i = 1; i <= n; i++) {
    dp[i] = dp[i >> 1] + (i & 1);  // ArrayIndexOutOfBounds at i = n
}

Write this instead

int[] dp = new int[n + 1];    // covers 0..n
for (int i = 1; i <= n; i++) {
    dp[i] = dp[i >> 1] + (i & 1);
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

DP over bit structure (offline popcount)

Code pattern to memorize

dp[0] = 0
for i in 1..n:
    dp[i] = dp[i >> 1] + (i & 1)
return dp

Rules to remember

1i >> 1 drops the lowest bit — it's i with its last digit chopped off, a smaller index already solved.
2i & 1 is the bit you chopped: 1 if i is odd, 0 if even.
3So bits(i) = bits(i / 2) + (last bit) — one O(1) recurrence reuses every earlier answer.
4Alternative recurrence: dp[i] = dp[i & (i - 1)] + 1 (Kernighan: clear lowest set bit, add 1).
5The output array of size n + 1 is the answer, not auxiliary space — extra space is O(1).

Use this pattern when

You need popcount for a whole range 0..n, not a single number
A bigger number's bit count can be built from a smaller, already-computed one
The interviewer asks you to beat the obvious 'call popcount n times'
Any problem where dropping/clearing one bit yields a solved subproblem

Choose another pattern when

You only need the count for one number → Brian Kernighan, no array (Number of 1 Bits)
You need the actual bits, not the count → shift-and-mask each position
n is tiny → the O(n log n) per-number popcount is fine and simpler to write
Memory is the constraint and you can't even store the output → reconsider the problem

Interview takeaway

Counting Bits is the gateway 'bit DP' problem: the count for i is the count for a smaller number (i >> 1) plus one cheap correction. The pattern — solve a number by reusing a structurally-smaller one — is the same instinct behind every overlapping-subproblem DP.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternBit DP / offline popcount. Recognise it when you need set-bit counts for a whole range and a larger number's answer can be built from a structurally smaller one (i >> 1 or i & (i - 1)). It's the bit-manipulation face of overlapping-subproblem DP.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Number of 1 Bits
The single-number building block: Brian Kernighan's n & (n - 1) popcount.
Hamming Distance
Coming soon
Popcount of a ^ b. Same counting machinery on the XOR of two numbers.
Number of Steps to Reduce a Number to Zero
Coming soon
Halve if even, subtract 1 if odd — steps = bits + (highest bit position). Same shift/odd structure.
Total Hamming Distance
Coming soon
Sum pairwise bit differences column by column — count set bits per position across all numbers.

Same pattern

←

Number of 1 Bits

Continue · Next problem

Reverse Bits

easyBit ManipulationLC #338Sometimes asked

Counting Bits

LCPractice

Bit Manipulation · 3 of 20 · 7 min

Given an integer n, return an array ans of length n + 1 such that for each i (0 ≤ i ≤ n), ans[i] is the number of 1's in the binary representation of i.

In plain English

Examples

Example 1

Input: n = 2
Output: [0, 1, 1]
Note: 0 → 0 bits, 1 → 1 bit, 2 (10) → 1 bit.

Example 2

Input: n = 5
Output: [0, 1, 1, 2, 1, 2]
Note: 0→0, 1→1, 2(10)→1, 3(11)→2, 4(100)→1, 5(101)→2.

Example 3

Input: n = 0
Output: [0]
Note: Only index 0, which has zero set bits.

Constraints

0 ≤ n ≤ 10⁵
ans.length == n + 1
ans[0] is always 0
Follow-up target: O(n) time, no popcount builtins

Clarifying questions4First question: Should the output include index 0?Explore questions

Q1.Should the output include index 0?
Yes — the array has length n + 1, covering 0..n inclusive, and ans[0] = 0.
Q2.Is n guaranteed non-negative?
Yes, 0 ≤ n ≤ 10⁵, so I don't need to worry about negative indices or the sign bit.
Q3.Does the output array count against my space complexity?
It's the required output, so it doesn't count as extra space. The DP uses only O(1) auxiliary space beyond the array.
Q4.Can I use a language builtin like Integer.bitCount in a loop?
That gives the O(n log n)... actually O(n) with hardware popcount, but the follow-up wants me to show the DP recurrence, so I'll implement it manually.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you can spot the overlapping subproblem hiding in the binary representation — that bits(i) relates to bits(i/2) — and turn an O(n log n) popcount loop into an O(n) DP.

Where candidates slip

Stopping at the per-number popcount (correct but O(n log n)), or deriving a recurrence but mis-handling the base case dp[0] = 0 or the odd-bit correction.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Per-Number Popcount (Brian Kernighan)	`O(n log n)`	`O(1)`	Open with this: 'I can count each number's bits independently — here's the O(n log n) version' — then improve it.	Read
2	DP — Reuse the Right-Shifted Result (Optimal)Optimal	`O(n)`	`O(1)`	The answer the follow-up wants. Say 'bits(i) = bits(i >> 1) + (i & 1): chop the last bit, look up the smaller number, add the bit back'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Per-Number Popcount (Brian Kernighan)

TimeO(n log n)SpaceO(1)

Open with this: 'I can count each number's bits independently — here's the O(n log n) version' — then improve it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You already know how to count the set bits of one number. What if you just do that for every i from 0 to n?

2Hint 2Explore hint

For each i, run Brian Kernighan's n & (n - 1) loop to count its bits and store the result at ans[i].

3Hint 3Explore hint

Each number costs O(number of set bits) ≤ O(log i), and there are n numbers → O(n log n) overall.

A · Core idea

Solve every index independently: for each i from 0 to n, count its set bits with Brian Kernighan's i & (i - 1) loop and store that in ans[i].

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 5

i=0

0 has no set bits

Stateans = [0]

Final result[0, 1, 1, 2, 1, 2]

C · Code with teaching comments

Reference implementation previewpublic int[] countBits(int n) { int[] ans = new int[n + 1]; for (int i = 0; i <= n; i++) { int x = i, count = 0; while (x != 0) {Explore the full code

solution.javaJava

Per-Number Popcount (Brian Kernighan) — reference

3 teaching notes

1
public int[] countBits(int n) {
2
    int[] ans = new int[n + 1];
3
    for (int i = 0; i <= n; i++) {
4
        // Copy i so we can destroy x while counting, keeping i for the index.
5
        int x = i, count = 0;
6
        // Kernighan loop — once per set bit of this number.
7
        while (x != 0) {
8
            x &= (x - 1);
9
            count++;
10
        }
11
        // Store this number's popcount, computed from scratch.
12
        ans[i] = count;
13
    }
14
    return ans;
15
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.15 lines

D · Why it works and complexityO(n log n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5n = 0 — Loop runs once for i = 0; inner while never executes → ans = [0].Explore edge cases

Edge cases handled

n = 0Loop runs once for i = 0; inner while never executes → ans = [0].
n = 1ans[0] = 0, ans[1] = 1 → [0, 1].

Pitfalls

Mutating i directly instead of a copy — you'd lose the loop index.
Calling a builtin popcount and claiming O(n) — true with hardware popcount, but it dodges the follow-up's intent to show a recurrence.
Off-by-one on the array size — it must be n + 1, not n.

03.2

Approach 2 of 2 · Optimal

DP — Reuse the Right-Shifted Result (Optimal)

TimeO(n)SpaceO(1)

The answer the follow-up wants. Say 'bits(i) = bits(i >> 1) + (i & 1): chop the last bit, look up the smaller number, add the bit back'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

How does the binary form of i relate to the binary form of i / 2 (i.e. i >> 1)?

2Hint 2Explore hint

i >> 1 is i with its lowest bit removed. So i has all the set bits of i >> 1, plus possibly the one bit you removed.

3Hint 3Explore hint

That removed bit is exactly i & 1. So dp[i] = dp[i >> 1] + (i & 1), and i >> 1 < i means it's already computed.

A · Core idea

Fill the answer array left to right. For each i, look up the already-computed count for i >> 1 and add the lowest bit i & 1.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 5

Interactive diagram

Each number reuses its right-shifted self

i=1

Active call / nodeSupporting contextReturned stateNot active

dp[i] points back to dp[i >> 1], a smaller index already solved; the label adds (i & 1).

Final result[0, 1, 1, 2, 1, 2]

C · Code with teaching comments

solution.javaJava

DP — Reuse the Right-Shifted Result (Optimal) — optimal

3 teaching notes

1
public int[] countBits(int n) {
2
    // Initialised to all zeros — gives dp[0] = 0 for free, the base case.
3
    int[] dp = new int[n + 1];
4
    // Start at 1 since dp[0] is already correct.
5
    for (int i = 1; i <= n; i++) {
6
        // Bits of i = bits of i with last digit chopped (i >> 1) plus that last bit (i
7
        // & 1).
8
        dp[i] = dp[i >> 1] + (i & 1);
9
    }
10
    return dp;
11
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.11 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5n = 0 — Loop body never runs; dp stays [0]. The zero-initialised array is already the answer.Explore edge cases

Edge cases handled

n = 0Loop body never runs; dp stays [0]. The zero-initialised array is already the answer.
n = 8dp[8] = dp[4] + 0 = 1 (8 = 1000). Powers of two correctly resolve to a single set bit via the chain 8→4→2→1.

Pitfalls

Forgetting dp[0] = 0 base case — though zero-initialising the array handles it implicitly.
Writing dp[i] = dp[i >> 1] + 1 unconditionally — you must add (i & 1), which is 0 for even i.
Using the recurrence with i decreasing or referencing a not-yet-filled index — always shift toward smaller, already-computed indices.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int[] countBits(int n) { int[] dp = new int[n + 1]; for (int i = 1; i <= n; i++) { dp[i] = dp[i >> 1] + (i & 1); }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Adding 1 instead of (i & 1)

Only odd numbers gain a set bit over their right-shifted half. Adding 1 for even i overcounts every even index.

Explore the code comparison

Don't write this

for i in range(1, n + 1):
    dp[i] = dp[i >> 1] + 1   # wrong: even i adds a phantom bit

Write this instead

for i in range(1, n + 1):
    dp[i] = dp[i >> 1] + (i & 1)   # add the actual lowest bit

Off-by-one array size

The output must cover 0..n inclusive — that's n + 1 entries. Sizing it n drops the answer for i = n.

Explore the code comparison

Don't write this

int[] dp = new int[n];        // missing index n
for (int i = 1; i <= n; i++) {
    dp[i] = dp[i >> 1] + (i & 1);  // ArrayIndexOutOfBounds at i = n
}

Write this instead

int[] dp = new int[n + 1];    // covers 0..n
for (int i = 1; i <= n; i++) {
    dp[i] = dp[i >> 1] + (i & 1);
}

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

DP over bit structure (offline popcount)

Code pattern to memorize

dp[0] = 0
for i in 1..n:
    dp[i] = dp[i >> 1] + (i & 1)
return dp

Rules to remember

1i >> 1 drops the lowest bit — it's i with its last digit chopped off, a smaller index already solved.
2i & 1 is the bit you chopped: 1 if i is odd, 0 if even.
3So bits(i) = bits(i / 2) + (last bit) — one O(1) recurrence reuses every earlier answer.
4Alternative recurrence: dp[i] = dp[i & (i - 1)] + 1 (Kernighan: clear lowest set bit, add 1).
5The output array of size n + 1 is the answer, not auxiliary space — extra space is O(1).

Use this pattern when

You need popcount for a whole range 0..n, not a single number
A bigger number's bit count can be built from a smaller, already-computed one
The interviewer asks you to beat the obvious 'call popcount n times'
Any problem where dropping/clearing one bit yields a solved subproblem

Choose another pattern when

You only need the count for one number → Brian Kernighan, no array (Number of 1 Bits)
You need the actual bits, not the count → shift-and-mask each position
n is tiny → the O(n log n) per-number popcount is fine and simpler to write
Memory is the constraint and you can't even store the output → reconsider the problem

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Number of 1 Bits
The single-number building block: Brian Kernighan's n & (n - 1) popcount.
Hamming Distance
Coming soon
Popcount of a ^ b. Same counting machinery on the XOR of two numbers.
Number of Steps to Reduce a Number to Zero
Coming soon
Halve if even, subtract 1 if odd — steps = bits + (highest bit position). Same shift/odd structure.
Total Hamming Distance
Coming soon
Sum pairwise bit differences column by column — count set bits per position across all numbers.

Same pattern

←

Number of 1 Bits

Continue · Next problem

Reverse Bits