#163

Counting Bits

easy

bit-manipulationdynamic-programming

Given a non-negative integer n, return an array ans of length n + 1 where ans[i] is the number of 1-bits (the Hamming weight) in the binary representation of i, for every i from 0 to n.

Example

Input: n = 2

Output: [0,1,1]

0 -> 0b0 (0 bits), 1 -> 0b1 (1 bit), 2 -> 0b10 (1 bit).

Constraints

0 <= n <= 10^5

Intuition

A first pass just counts each number's bits on its own: for every i from 0 to n, repeatedly check the lowest bit and shift right until nothing's left, tallying however many bits were set.

function countingBits(n) {
  const ans = new Array(n + 1);
  // Every number from 0 to n gets its own, independent bit-counting pass.
  for (let i = 0; i <= n; i++) {
    let x = i;
    let count = 0;
    // Peel off the lowest bit and shift right until nothing's left.
    while (x > 0) {
      count += x & 1; // tally the lowest bit
      x >>= 1; // drop it and look at the next bit up
    }
    ans[i] = count;
  }
  return ans;
}

Brute force — count each number's bits independently, one shift per bit position: O(n log n).

This is O(n log n) — each of the n numbers pays for its own O(log n) walk down through its bits, even though most of those numbers share almost all their bits with a number counted just a few steps earlier. Can we do better?

The key observation: dropping x's lowest bit (x >> 1) is the same as halving it, and the bit count of that halved value — dp[x >> 1] — has already been computed earlier in the same pass, since x >> 1 is always smaller than x. So dp[x] = dp[x >> 1] + (x & 1) reuses that earlier answer instead of recounting x's bits from scratch. This is dynamic programming over the integers themselves rather than over array indices — the same overlapping-subproblems idea, just with the "index" doubling as the value being decomposed.

The stored solution's variable names already match this walkthrough — dp is the array being filled and x is the index (and value) being decomposed — so no bridging is needed.

Walking it through:

dp[x] = set bits in x, for x = 0..7 (n = 7)

x↓

dp[0] = 0

Base case: zero has no set bits.

x↓

dp[1] = dp[0] + (1 & 1) = 0 + 1 = 1

1 is odd (its lowest bit is 1), and halving it (1 >> 1 = 0) lands right back on the base case.

x↓

dp[2] = dp[1] + (2 & 1) = 1 + 0 = 1

2 is even (lowest bit 0) — it reuses dp[1] (2 >> 1 = 1) unchanged.

x↓

dp[3] = dp[1] + (3 & 1) = 1 + 1 = 2

3 is odd; 3 >> 1 = 1, so it reuses dp[1] and adds its own lowest bit back.

x↓

dp[4] = dp[2] + (4 & 1) = 1 + 0 = 1

Power-of-two boundary: dp resets to 1. 4 >> 1 = 2 skips back two indices, not one — the recurrence reads whatever dp[x >> 1] holds, which needn't be the immediately preceding cell.

x↓

dp[7] = dp[3] + (7 & 1) = 2 + 1 = 3

Final state: 7 is 0b111, three set bits — matching what the brute force would count the slow way.

Optimization

DP over dp[x] = dp[x >> 1] + (x & 1)

Dropping the lowest bit of x (x >> 1) halves it, and its bit count has already been computed earlier in the loop as dp[x >> 1]. That count is exactly the number of set bits above the lowest bit of x, so we just add back x's own lowest bit (x & 1). Building the array left to right this way visits each index once with only O(1) work per step, instead of counting each number's bits independently.

O(n) time, O(n) space for the (required) output array.

function countingBits(n) {
  const dp = new Array(n + 1);
  dp[0] = 0;
  for (let x = 1; x <= n; x++) {
    // dp[x >> 1] already counted every set bit above the LSB; add x's own LSB back.
    dp[x] = dp[x >> 1] + (x & 1);
  }
  return dp;
}

Complexity analysis

Time complexity: O(n). Here's why:

Building the array visits each index x from 1 to n exactly once.
At each index, computing dp[x >> 1] + (x & 1) is one array lookup plus two O(1) bitwise ops.

So the whole array fills in a single pass — O(n) — instead of the brute force's O(n log n) of re-deriving every count's bits from scratch.

Space complexity: O(n). Here's why:

The dp array holds n + 1 entries, one per index from 0 to n — and it is the function's required return value.
Beyond the array itself, only the loop variable x is extra — O(1).

Counting only auxiliary space (not the required output), the algorithm uses O(1) extra; counting the output too, the total is O(n).

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
n = 0	[0]	Smallest possible input — a single index, zero set bits.
n = 6	[0,1,1,2,1,2,2]	General case, landing just below the next power-of-two boundary (8).
n = 9	[0,1,1,2,1,2,2,3,1,2]	One index past a power-of-two boundary — dp[8] resets to 1, then dp[9] climbs back to 2.
n = 20	[0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2]	Larger, unaligned n — the final index isn't itself a power-of-two boundary.
n = 31	[0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5]	One index short of the next power-of-two boundary (32) — the run of a full block of bit widths.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor