easy

Counting Bits

For every number up to n, count how many bits are set to 1 in its binary form.

1. Define the problem

Counting Bits

Given an integer n, return an array ans of length n + 1 where ansi is the number of 1 bits in the binary representation of i, for every i from 0 to n. Build the answer with a running relationship : i shifted right by one bit is i with its lowest bit dropped, so ansi = ans[i >> 1] + (i & 1) — reuse work already done instead of recomputing from scratch.

Constraints

  • 0 ≤ n ≤ 105

Example

Inputn = 5
Output[0, 1, 1, 2, 1, 2]

Explanation 0=0, 1=1, 10=1, 11=2, 100=1, 101=2 set bits.

2. Know the words first

In plain terms

i >> 1
Right shift by 1 divides i by two and discards the remainder — the same as removing the lowest bit of its binary form.
i & 1
Masks off every bit except the lowest one, giving i's parity (0 or 1).
3. Visualize the solution

Reuse ans[i >> 1] to build each new count

Reuse ans[i >> 1] to build each new count
Statusinit

ans[0] = 0 by definition — 0 has no set bits.

What happens in this step

ans[0] = 0

0 has no bits at all, so it has zero set bits by definition. Every other ans[i] below is built from this base case.
Step 1 of 6

Steps to visualize

  1. Set ans0 = 0, since 0 has no set bits.
  2. For each i from 1 to n, look up ans[i >> 1], already computed earlier in the array.
  3. Add (i & 1) — 1 if i is odd, 0 if i is even.
  4. Store that sum as ansi and move to the next value.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Reuse ans[i >> 1] to build each new count
Statusinit

ans[0] = 0 by definition — 0 has no set bits.

What happens in this step

ans[0] = 0

0 has no bits at all, so it has zero set bits by definition. Every other ans[i] below is built from this base case.
Step 1 of 6
5. Solution

Solution

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

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

  return ans;
}
Time
O(n)
Space
O(n) for the output array
6. Test cases

Test cases

InputExpectedCovers
n = 5[0, 1, 1, 2, 1, 2]example from the docstring
n = 0[0]smallest valid input, just 0
n = 1[0, 1]boundary case with a single non-zero entry
n = 8[0, 1, 1, 2, 1, 2, 2, 3, 1]n itself is a power of two, resetting to a single set bit
n = 2[0, 1, 1]small even n
n = 10[0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2]a longer run spanning multiple power-of-two boundaries

Keep reading