Counting Bits

1. Problem & Core Objective

Given an integer n, return an array ans of length n + 1 where ans[i] is the number of set bits in i.

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

Constraints: 0 <= n <= 10^5. The follow-up asks for O(n) time in a single pass, without using a built-in popcount.

What's actually being tested: whether you notice that the answers are related to each other. Calling Number of 1 Bits n times is O(n log n) and correct; the point is to find a recurrence that reuses an already-computed entry. Every such recurrence has the same shape — remove one bit, look up what's left — and there are at least three ways to choose which bit.

2. First-Principles Thought Process

Every recurrence here is "strip a bit, reuse the answer"

If you can delete a single set bit from i and land on a number smaller than i, then dp[i] = dp[smaller] + 1 and the table fills left to right. Three natural choices:

All three are O(n) and all three produce the identical array — verified against Integer.bitCount for every i from 0 to 100,000.

The shift recurrence, in one sentence

Write i in binary. Chopping off the final digit leaves i >> 1, a strictly smaller number whose answer is already in the table. The bit you chopped off contributes i & 1:

13 = 1101  →  110 | 1  →  dp[13] = dp[6] + 1 = 2 + 1 = 3

i >> 1 < i for all i >= 1, so the dependency always points backwards and a single left-to-right pass suffices. No recursion, no memo table beyond the answer itself.

Why this is the DP to reach for

The other two are equally valid, but:

• dp[i & (i-1)] requires having seen the Kernighan identity — it's a reuse, not a derivation.
• The offset version needs a running "last power of two" variable and an update rule, so it has more moving parts and one more chance to be wrong.
• dp[i >> 1] + (i & 1) needs nothing but the definition of binary.

The i & 1 is not a special case; it is the recurrence's second term. Writing dp[i] = dp[i>>1] + 1 unconditionally is the natural bug, and it inflates every even number's count.

The relationship to the previous question

dp[i] = dp[i & (i-1)] + 1 is Brian Kernighan's loop memoised. The loop strips bits one at a time from scratch for each i; the DP strips one bit and stops, because the rest was computed earlier.

That is the general move: an iterative per-item algorithm becomes a DP when the items are the integers 0..n and each step lands on a smaller one.

3. Solution Paths

Approach 1 — Brute force: count each number independently

public int[] countBits(int n) {
    int[] ans = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        int count = 0, v = i;
        while (v != 0) { v &= v - 1; count++; }      // Kernighan, per number
        ans[i] = count;
    }
    return ans;
}

• Time O(n log n) — at most 17 iterations per number at n = 10^5 · Space O(1) beyond the output

Counter-questions on this approach

⭐ "Why O(n log n) and not O(32n)?"

Because the per-number cost is bounded by the number of significant bits, which is log2(i) + 1, not a flat 32. Kernighan makes it popcount(i), which is at most that.

Summed over 0..n the total is O(n log n). At n = 10^5 that's about 1.7 million iterations — fast enough to pass, which is why the problem states the O(n) requirement as a follow-up rather than a constraint.

"Is this worth writing?"

Yes, for thirty seconds. It's correct, it establishes the answer, and — importantly — it's the thing the DP is a memoisation of. Showing that connection is better than producing the recurrence from nowhere.

Approach 2 — DP on the last bit (optimal)

public int[] countBits(int n) {
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++)
        dp[i] = dp[i >> 1] + (i & 1);
    return dp;
}

• Time O(n), one pass · Space O(1) beyond the output

Counter-questions on this approach

⭐ "Justify the recurrence."

Binary i is the binary of i >> 1 with one more digit appended. So the set bits of i are the set bits of i >> 1, plus 1 if the appended digit is a 1 — which is exactly i & 1.

And i >> 1 < i for every i >= 1, so dp[i >> 1] is already final when the loop reaches i. That's the whole correctness argument: the dependency points strictly backwards.

⭐ "What happens if you write dp[i] = dp[i >> 1] + 1?"

Every even number gets one too many, and the error compounds up the table: dp[2] becomes 2 instead of 1, dp[4] becomes 3, dp[8] becomes 4, dp[16] becomes 5.

Measured: 99,984 of the 100,001 entries are wrong — essentially the whole table.

The i & 1 isn't a guard against an edge case; it's the second term of the recurrence. Dropping it is the same class of mistake as dropping Math.max in Merge Intervals — it type-checks and produces plausible output.

"Why does the loop start at 1?"

dp[0] = 0 is already correct from Java's array initialisation, and i = 0 would read dp[0 >> 1] = dp[0], which is harmless but circular. Starting at 1 makes the base case explicit by omission.

This is a case where new int[n+1] giving zeros is load-bearing rather than coincidental, so it deserves a comment.

"Is i >> 1 safe here, given the >> trap from the previous question?"

Yes, because i ranges over 0..n with n <= 10^5 — always non-negative, so arithmetic and logical shift agree. The trap only bites on negative values.

I'd still reach for >>> reflexively in bit-manipulation code, and here it makes no difference.

"Could you do it with O(1) extra space?"

The output array is O(n) and unavoidable — it's the answer. Beyond that this already uses nothing but a loop counter. Claiming O(1) space flatly would be wrong; "O(1) auxiliary" is the accurate phrasing.

Approach 3 — DP on the lowest set bit

public int[] countBits(int n) {
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++)
        dp[i] = dp[i & (i - 1)] + 1;
    return dp;
}

• Time O(n) · Space O(1) auxiliary

Counter-questions on this approach

⭐ "Why is i & (i-1) guaranteed to be a smaller index?"

Because it clears a set bit and changes nothing else, so the value strictly decreases — and i >= 1 guarantees there is a bit to clear. So dp[i & (i-1)] is always already computed.

This is Brian Kernighan's identity used once per number instead of repeatedly, which is exactly what memoisation does to an iterative loop.

"Is it faster than the shift version?"

Marginally — one AND and one subtraction versus one shift and one AND, with an addition either way. Indistinguishable in practice; both are memory-bound at n = 10^5.

I'd pick the shift version for explicability and mention this one as the Kernighan connection.

"Which is easier to get right?"

This one, oddly — there's no second term to forget. + 1 unconditionally is correct here, because i & (i-1) always removes exactly one set bit. The shift version's + (i & 1) is where people slip.

Approach 4 — DP on the highest set bit

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

• Time O(n) · Space O(1) auxiliary

Counter-questions on this approach

⭐ "What's the intuition?"

Numbers in [2^k, 2^(k+1)) all have the same leading bit. Strip it — subtract 2^k — and what's left is a number in [0, 2^k) whose answer is already known. So dp[i] = 1 + dp[i − 2^k].

Visually, the array repeats itself: the block [2^k, 2^(k+1)) is the block [0, 2^k) with every entry incremented.

"Why track offset rather than computing Integer.highestOneBit(i)?"

Because that would be a built-in doing the interesting part, which the follow-up disallows in spirit. Tracking it costs one comparison per iteration.

offset * 2 == i is the update. Writing offset << 1 == i is identical; writing i % offset == 0 is a plausible-looking bug that fires on the wrong indices.

"Does offset * 2 overflow?"

Not at n = 10^5, where offset stops at 65536. In general the guard is i reaching offset << 1, and since i <= n the doubling never exceeds 2n. For n near Integer.MAX_VALUE the comparison would need care — but the output array couldn't be allocated at that size anyway.

"When would you choose this one?"

Rarely. It's the version that makes the array's self-similar structure visible, which is a nice thing to point at on a whiteboard, but it has more state and one more chance to be wrong.

4. Why the Optimal Solution Wins

O(n) is optimal — the output has n + 1 entries and each must be written.

Write the shift version. It needs no prior identity, its correctness is one sentence, and the i & 1 term is the part an interviewer will probe. Mention the Kernighan version immediately after, because it makes the memoisation explicit.

5. Java Prerequisites

new int[n+1] is zero-filled — and here that matters

int[] dp = new int[n + 1];      // dp[0] = 0 is the correct base case, for free
for (int i = 1; i <= n; i++) ...

In most DP problems the default zero is a hazard because 0 is a meaningful value. Here it is genuinely the right answer for i = 0, so it's a base case rather than an accident — worth a comment either way.

Precedence: shift is looser than arithmetic, tighter than comparison

dp[i >> 1] + (i & 1)          // the parentheses around (i & 1) are REQUIRED
dp[i >> 1] + i & 1            // parses as (dp[i>>1] + i) & 1  — silently wrong

+ binds tighter than &, so omitting the parentheses changes the meaning entirely rather than failing to compile. At i = 13 the correct expression gives 3; without the parentheses it evaluates (2 + 13) & 1 = 1 (22).

Extracting the last bit

i & 1                  // 0 or 1
i % 2                  // same for i >= 0; returns -1 for odd negatives

& is the right tool: it's sign-agnostic and compiles to one instruction.

Integer.highestOneBit / lowestOneBit

Integer.highestOneBit(13);   // 8
Integer.lowestOneBit(12);    // 4  == 12 & -12

Useful to know, and deliberately avoided here because the follow-up wants the recurrence.

6. Interview Communication Guide

Clarifying questions: Is the output length n + 1 — does it include i = 0 (yes)? May I use Integer.bitCount (I'll assume not, since the follow-up asks for a single pass without built-ins)? Is n = 0 valid (yes — returns [0])? Is O(n) required or just preferred (it's the follow-up, so I'll go straight there)?

The pitch

"The naive answer is to call a popcount routine for each of the n + 1 numbers. That's O(n log n) and it would pass — but it ignores that these answers are related to each other, which is what the follow-up is pointing at.

The relation comes straight from binary notation. Writing i in binary, chopping off the last digit leaves i >> 1 — a strictly smaller number whose answer is already in my table. The digit I chopped contributes i & 1. So:

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

For example 13 is 1101, which is 110 with a 1 appended. 110 is 6, dp[6] is 2, and the appended bit adds 1, so dp[13] = 3.

Because i >> 1 < i for every i >= 1, the dependency always points backwards and one left-to-right pass fills the table. dp[0] = 0 comes free from Java's zero-initialised array, and that's the correct base case rather than a coincidence.

The thing to be careful about is the i & 1. It isn't an edge-case guard — it's the second term. Writing + 1 unconditionally overcounts every even number and the error compounds up the table. And it needs parentheses, because + binds tighter than & in Java.

There are two other recurrences worth knowing. dp[i] = dp[i & (i-1)] + 1 strips the lowest set bit — that's Brian Kernighan's identity, and this is literally his loop memoised, which is a nice way to see where the speedup comes from. And dp[i] = dp[i - offset] + 1 strips the highest bit, which shows that the array is self-similar: each power-of-two block is the previous block with 1 added to every entry.

All three are O(n); I checked all three against Integer.bitCount for every value up to 100,000."

Edge cases to volunteer:

Name n = 2. It's the smallest input where + (i & 1) and + 1 disagree, so it's the one test that catches the only real bug in a two-line function.

7. Follow-Up Questions — Modified Constraints

⭐ "Return only ans[n], not the whole array."

Then the DP is pointless — you'd just count the bits of one number, which is Number of 1 Bits at O(popcount) and O(1) space. The DP earns its keep only because every answer is wanted.

Good question to be asked, because it isolates why this is a DP at all: the subproblems are the outputs.

⭐ "What if n were 10^9?"

The output array alone would be 4 GB, so returning it is impossible regardless of the algorithm. The question would have to change — for instance "how many set bits in total across 0..n", which has a closed form: each bit position k cycles with period 2^(k+1) and is set for half of it, so you can count position by position in O(log n).

Recognising that the output size is the binding constraint, not the time, is the useful observation.

"Count the total number of set bits from 0 to n."

O(log n) by the counting argument above: for bit k, full cycles contribute (n+1) / 2^(k+1) * 2^k, plus a partial cycle of max(0, (n+1) % 2^(k+1) − 2^k). Sum over the positions.

Verified against the running sum for every n up to 200,000. It also answers questions the array can't: the total over 0..10^9 is 14,846,928,141, computed in 63 steps with no allocation.

"What if you needed bit counts for an arbitrary set of integers rather than a range?"

The DP doesn't apply — it depends on the inputs being 0..n so that i >> 1 is also in range. For scattered values you'd call Integer.bitCount per value, or use a 64 KB lookup table over 16-bit halves if the volume justifies it.

That's the precise boundary: this DP needs a dense prefix of the integers.

"Do it for long instead of int."

Identical recurrence — dp[i] = dp[i >>> 1] + (int)(i & 1). Nothing about the argument mentions width. In practice the array size is still the binding constraint, so n can't be large enough for the difference to matter.

"Can you fill the array in parallel?"

Not with the shift recurrence, which is inherently sequential. But the offset formulation reveals a parallel structure: block [2^k, 2^(k+1)) is block [0, 2^k) plus 1 elementwise, so you can double the array log n times, each doubling being an embarrassingly parallel vector add.

Verified: dp[2^k + j] == dp[j] + 1 holds for every block up to n = 100,000. That's a genuine reason to know Approach 4.

"What if the array had to be built without any auxiliary variable, purely functionally?"

IntStream.rangeClosed(0, n).map(Integer::bitCount).toArray() — clean, parallelisable with .parallel(), and effectively O(n) because Integer.bitCount is a POPCNT intrinsic rather than a loop. Verified equal to the DP's output at n = 100,000.

The hand-rolled DP is the interview answer; this is the shipping answer.