Counting Bits

Problem in Plain English

Build an array where entry i holds the number of 1 bits in the binary form of i, for every i from 0 up to n.

Problem Statement

Given an integer n, return an array ans of length n + 1 where ans[i] counts the number of 1 bits in the binary form of i, for every i from 0 to n.

Counting each number from scratch repeats work, because smaller answers already reveal larger ones: stripping the lowest set bit, or halving the number, lands on a value already computed. Aim for one linear pass with no built-in bit counter.

Constraints

$0 \le n \le 10^5$

Examples

Example 1

Input: n = 2
Output: [0, 1, 1]

0 has zero ones, 1 has one, and 2 (10 in binary) has one.

Example 2

Input: n = 5
Output: [0, 1, 1, 2, 1, 2]

3 (11) has two ones, 4 (100) has one, and 5 (101) has two.

Example 3

Input: n = 0
Output: [0]

The range still includes zero. Its binary representation has no set bits, so the returned array has one entry rather than being empty.

Intuition

Binary digits describe how many powers of two make a number; count only the digits equal to one. Example 1 needs answers for 0, 1 and 2: their binary forms 0, 1 and 10 contain 0, 1 and 1 ones. Counting each separately works, but removing the last digit of 2 leaves 1, whose answer is already available. The removed digit contributes either zero or one, so smaller answers can build the entire array.

Approaches

Count Each Number

Solution Details

Reveal Count Each Number: intuition, complexity, and code

Intuition

Each number can be measured on its own by clearing its lowest set bit again and again: x & (x - 1) drops exactly one 1 per round, so the round count is the answer. Repeating that independent measurement for all 0 to n is correct but re-counts shared structure every time.

Step-by-Step Logic

Read Example 1 as n = 2 and allocate ans = [0, 0, 0].
For i = 0: x = 0 needs no rounds, so ans[0] = 0.
For i = 1 (binary 1): one clearing round 1 to 0, so ans[1] = 1.
For i = 2 (binary 10): one clearing round 2 to 0, so ans[2] = 1.
All numbers are measured: return [0, 1, 1], the expected output.

Why It Works

For a positive x, subtracting one flips the lowest one to zero and turns only the zeros below it into ones. AND with the old x removes those new ones and clears exactly that lowest set bit; higher bits are unchanged. After k rounds, exactly k original ones have been removed. Reaching zero therefore means the counter equals the original population count. Applying this independently to every index from 0 through n produces every required entry, including zero.

Dry Run

Count Each Number: variable states at each step
`i`	Binary	Clearing rounds	`ans[i]`
`0`	`0`	none	`0`
`1`	`1`	`1` to `0`	`1`
`2`	`10`	`2` to `0`	`1`
return	-	-	`[0, 1, 1]`

Complexity Analysis

Time Complexity

O(n \log(n+1))

Space Complexity

O(n)

For n >= 1, each number uses at most floor(log2 n) + 1 bit-clearing rounds; across a full range the worst-case total is Theta(n log(n+1)). The returned n + 1 element array allocates O(n) space. Apart from that required output, counters and helper calls use O(1) auxiliary space; the helper is not recursive. Values are at most 100000, so all shifts and masks fit fixed-width integers.

Code

Solution.java

1class Solution {2    public int[] countBits(int n) {3        int[] ans = new int[n + 1];4        for (int i = 0; i <= n; i++) {5            ans[i] = popcount(i);6        }7        return ans;8    }9
10    private int popcount(int x) {11        int bits = 0;12        while (x != 0) {13            // Clear exactly one set bit, leaving all higher bits unchanged.14            x &= (x - 1);15            bits++;16        }17        return bits;18    }19}

Hints

Hint 1

Compare neighbors: 4 (100) has the same count as 2 (10), and 5 (101) has one more. What operation turns one into the other?

Hint 2

Shifting right by one halves the number and drops its last bit; that bit equals i & 1.

Hint 3

Fill dp[i] = dp[i >> 1] + (i & 1) left to right from dp[0] = 0, since the halved index is always already computed.

Edge Cases

n = 0 returns [0]. The DP loop never runs; the baseline evaluates zero without clearing any bit.
Powers of two such as 8 (binary 1000) have exactly one set bit. The recurrence follows dp[8] = dp[4] = dp[2] = dp[1] = 1, with dp[1] = dp[0] + 1.
The maximum n = 100000 still fills in one pass with no per-number inner loop.

Common Mistakes and Interview Tips

Recounting every number is a valid baseline, but does not meet the linear-time follow-up; explain how the DP recurrence avoids that repeated work.
Writing dp[i >> 1] + i & 1 without parentheses where the language parses it as (dp[i >> 1] + i) & 1.
Sizing the answer as length n instead of n + 1, dropping the entry for n itself.

Key Takeaway

When answers for 0 to n build on each other, look for a one-step reduction — here halving — that turns earlier results into current ones.