Counting Bits

Examples

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

0 is 0b0 (zero 1 bits). 1 is 0b1 (one 1 bit). 2 is 0b10 (one 1 bit).

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

0=0b0, 1=0b1, 2=0b10, 3=0b11 (two 1 bits), 4=0b100 (one 1 bit), 5=0b101 (two 1 bits).

Constraints

• 0 <= n <= 10^5

Approach

The direct way is to count the 1 bits of each number from 0 to n completely independently, using the same bit-clearing trick you'd use to count the bits of just one number. That's correct, but it redoes a lot of work, since smaller numbers' answers were already computed earlier and thrown away.

A much cheaper approach builds every answer directly from a smaller, already-computed one. Shifting any number i right by one bit (i >> 1) simply drops its last bit and is exactly equal to Math.floor(i / 2) - a smaller number whose 1-bit count was already found earlier in the same pass. The number of 1 bits in i is then just that smaller number's count, plus 1 more if the bit that got dropped (i & 1) was itself a 1. That turns the whole problem into a single pass building up a table of answers, each one reusing an earlier result instead of recomputing anything from scratch.

Solutions

Brute Force - Count Each Number Independently

For every number from 0 to n, count its 1 bits from scratch, using the 'clear the lowest set bit' trick (or an equivalent bit-by-bit check).

function countBits(n) {
  const result = new Array(n + 1).fill(0);

  for (let i = 0; i <= n; i++) {
    let num = i;
    let count = 0;
    while (num > 0) {
      count += num & 1;
      num = num >>> 1;
    }
    result[i] = count;
  }

  return result;
}

Time: O(n log n) - about O(log i) work for each of the n numbers · Space: O(n), for the output list

Optimal - Build Each Answer From a Smaller One

For each number i, its bit count equals the bit count of i >> 1 (i with its last bit dropped, already computed earlier in the same pass) plus 1 if that dropped bit (i & 1) was itself a 1.

function countBits(n) {
  const result = new Array(n + 1).fill(0);

  for (let i = 1; i <= n; i++) {
    result[i] = result[i >> 1] + (i & 1);
  }

  return result;
}

Time: O(n) · Space: O(n), for the output list