#338 - Counting Bits

EasyBit Manipulation

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

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

Solution Space

Try it

/**
 * Returns the number of 1-bits for every integer from 0 to n.
 *
 * Key recurrence: popcount(i) = popcount(i >> 1) + (i & 1).
 * i >> 1 already computed (smaller index), and i & 1 checks the last bit.
 *
 * @param n Upper bound (inclusive)
 * @returns Array of bit counts
 */
export function countBits(n: number): number[] {
  const ans = new Array<number>(n + 1).fill(0);

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

  return ans;
}

Approach: DP on bit shift – `popcount(i) = popcount(i >> 1) + (i & 1)`. The right-shifted value is always a smaller index, so it's already computed.

Time: O(n) – single pass.

Space: O(n) – the output array.

#136 Single Number

#1318 Minimum Flips to Make a OR b Equal to c