Counting Bits

The problem

Given a whole number n that is 0 or more, return a list of n + 1 counts. The count at position i says how many bits are 1 when the number i is written in binary, as a row of bits that are each 0 or 1. The list covers every number from 0 to n, in order. For n = 0 the list is [0].

What to write

function solve(n: number): number[]

Input
n = 2

Output
[0,1,1]

Input
n = 5

Output
[0,1,1,2,1,2]

Constraints

Integer n from 0 to 10,000.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   n can be 10,000, so the list holds up to 10,001 counts. Counting the 1 bits of every number separately is fast enough at that size, so speed will not stop you. Notice the shape of the answer instead: it is a count for every number from 0 up, in order, and each one stays in the list.

2. Hint 2: Ask a smaller question

   Write the numbers 0 to 7 in binary and put each one's count of 1 bits beside it. Compare 6, which is 110, with 4, which is 100: one bit differs. How do their counts differ? For every number above 0 in your table, can you find a smaller number that differs from it in a single bit?

3. Hint 3: Name the pattern

   You are asked for the count of every number from 0 to n, and each count can be read off the count of a smaller number: clear one 1 bit and the count drops by exactly 1. Filling a list in order, each answer built from an earlier one, is one-dimensional dynamic programming. Read the lesson on one-dimensional dynamic programming.

4. Hint 4: State the invariant

   A number has one more 1 bit than the same number without its lowest 1 bit, the rightmost 1. i AND (i - 1) clears that bit: AND keeps a 1 only where both numbers have one, and i - 1 has a 0 there. The result is smaller than i, so its count is already in the list.

5. Hint 5: Sketch the pseudocode

   Make a list of n + 1 zeros. For each i from 1 up to n: list[i] = list[i AND (i - 1)] + 1. Return the list. The slot for 0 stays 0, which is right because 0 has no 1 bits, so the loop starts at 1.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Removing the lowest set bit with i & (i - 1) gives a smaller number with one fewer set bit. Add 1 to its already-computed count.

The slow way

Count the 1 bits of each number from 0 to n separately, as Number of 1 Bits does, with one round per 1 bit. It is correct. For n = 10,000 it takes 64,613 rounds in all, where one round per number would be 10,000. Each count is worked out from nothing, although 7 (111) and 6 (110) share every bit but one.

The insight

A bit that is 1 is called a set bit. Clear the lowest one, the rightmost 1, and you get a smaller number with one 1 bit fewer: 6 is 110, and without that bit it is 100, which is 4. The list is filled from 0 upward, so the count for 4 is already there when you reach 6. The count for 6 is that count plus 1.

Step by step

1. Make a list with a count of 0 for every number from 0 to n. The answer has one slot per number from 0 to n, so n + 1 slots. The slot for 0 is already right, because 0 has no 1 bits.
2. Fill in the counts from 1 up to n, smallest number first. Each count is built from the count of a smaller number. Going upward, that smaller number's slot holds its final count before it is needed.
3. Take the count of the number without its lowest 1 bit and add 1. The number AND itself minus 1 is the number without its lowest 1 bit, where AND, written &, keeps a 1 only where both have one. That bit is the only difference, so the count is 1 higher.
4. Return the list of counts. Every slot from 0 to n now holds the number of 1 bits of its own position, in order, which is the list the problem asks for.

The same numbered steps are the comments in each solution.

function solve(n) {
  // 1. Make a list with a count of 0 for every number from 0 to n
  const out = Array(n + 1).fill(0);
  // 2. Fill in the counts from 1 up to n, smallest number first
  for (let i = 1; i <= n; i++) {
    // 3. Take the count of the number without its lowest 1 bit and add 1
    out[i] = out[i & (i - 1)] + 1;
  }
  // 4. Return the list of counts
  return out;
}

function solve(n: number): number[] {
  // 1. Make a list with a count of 0 for every number from 0 to n
  const out = Array(n + 1).fill(0);
  // 2. Fill in the counts from 1 up to n, smallest number first
  for (let i = 1; i <= n; i++) {
    // 3. Take the count of the number without its lowest 1 bit and add 1
    out[i] = out[i & (i - 1)] + 1;
  }
  // 4. Return the list of counts
  return out;
}

def solve(n):
    # 1. Make a list with a count of 0 for every number from 0 to n
    out = [0] * (n + 1)
    # 2. Fill in the counts from 1 up to n, smallest number first
    for i in range(1, n + 1):
        # 3. Take the count of the number without its lowest 1 bit and add 1
        out[i] = out[i & (i - 1)] + 1
    # 4. Return the list of counts
    return out

Example 2, traced

Input
n = 5

Output
[0,1,1,2,1,2]

Why it works

Subtracting 1 flips a number's lowest 1 bit and the 0s to its right, so AND with the number itself keeps everything except that bit. The result has exactly one 1 bit fewer and is smaller, so its count is already final in the list. Building each answer from a stored earlier answer is dynamic programming, here one-dimensional: one list of counts.

Time and space

Time O(n), extra space O(n) output. The loop runs once for each number from 1 to n and does the same few operations every time, so the time is O(n). The only memory used is the list of n + 1 counts, which is the output itself, so the space is O(n).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Start the loop at 1, not 0. At 0 the slot for 0 is set to its own count plus 1. Every later count builds on it and is 1 too high: n = 2 returns [1, 2, 2].
• The list needs n + 1 slots, not n. With n slots, n = 0 returns an empty list. For larger n Python stops with an index error, while JavaScript grows the list and hides the mistake.
• The loop has to include n itself. Stopping one number early leaves the last slot at its starting 0: n = 2 returns [0, 1, 0] instead of [0, 1, 1].

Pattern

One-dimensional dynamic programming. Builds on Number of 1 Bits and Climbing Stairs.

Keep going