Binary Counter Exhibit

Easybit manipulationAlso known as Counting Bits

A science museum has a wall of light bulbs that counts in binary. Each second it shows the next number: 0, then 1, then 10, then 11, then 100, and so on, with a lit bulb for every 1 bit.

The museum's electrician is planning the power supply. For a show that counts from 0 up to n, she wants to know how many bulbs are lit at each number.

Your task

Write litBulbs(n). Return a list of length n + 1 where position i holds the number of 1 bits in the binary form of i.

Aim for O(n) total time: work out each count from a count you already have, instead of examining every bit of every number.

litBulbs(n: int) → int[]

Examples

Example 1

Input

n = 5

Output

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

Why

0 = 0, 1 = 1, 2 = 10, 3 = 11, 4 = 100, 5 = 101. Counting the 1s gives 0, 1, 1, 2, 1, 2.

Example 2

Input

n = 8

Output

[0, 1, 1, 2, 1, 2, 2, 3, 1]

Why

The count drops back to 1 at 4 and at 8. Each power of two lights one bulb, after a run where many bulbs were lit (7 = 111 has three).

Constraints

0 ≤ n ≤ 100,000

Start with brute force

For each number from 0 to n, count its 1 bits one at a time: check the last bit, shift right, repeat until the number is 0.

Each number takes up to about 17 steps when n is 100,000, so this is O(n log n). It is not slow, but it throws away work: the count for 12 already contains the count for 6, which you computed a moment ago.

Hints

0 of 4 shown

Hint 1
Write 6 and 3 in binary: 110 and 11. Then 10 and 5: 1010 and 101. How is each pair related, and what does that do to the number of 1 bits?
Hint 2
i >> 1 (that is, i divided by 2, rounded down) is i with its last bit chopped off. Every other bit stays the same.
Hint 3
So the bulbs lit for i are the bulbs lit for i >> 1, plus one more if the bit you chopped off was a 1. How do you read that last bit?
Hint 4
Fill the list from 0 upward: counts[0] = 0, and counts[i] = counts[i >> 1] + (i & 1). i >> 1 is always smaller than i, so its count is already there.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

Shifting right by one drops the last bit and keeps the rest. So every number shares all but one bit with a smaller number whose count you already know.

Trace up to 6:

counts[0] = 0.
1 is 1. 1 >> 1 = 0, last bit 1. counts[1] = 0 + 1 = 1.
2 is 10. 2 >> 1 = 1, last bit 0. counts[2] = 1 + 0 = 1.
3 is 11. 3 >> 1 = 1, last bit 1. counts[3] = 1 + 1 = 2.
4 is 100. 4 >> 1 = 2, last bit 0. counts[4] = 1 + 0 = 1.
5 is 101. 5 >> 1 = 2, last bit 1. counts[5] = 1 + 1 = 2.
6 is 110. 6 >> 1 = 3, last bit 0. counts[6] = 2 + 0 = 2.

A tempting shortcut is "one more bulb than the previous number". It fails at every carry: 7 has three bulbs lit, but 8 has only one.

Reference solution

function litBulbs(n) {
  const counts = new Array(n + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    // i >> 1 is i without its last bit; i & 1 is that last bit
    counts[i] = counts[i >> 1] + (i & 1);
  }
  return counts;
}

def lit_bulbs(n):
    counts = [0] * (n + 1)
    for i in range(1, n + 1):
        # i >> 1 is i without its last bit; i & 1 is that last bit
        counts[i] = counts[i >> 1] + (i & 1)
    return counts

TimeO(n)One shift, one AND and one addition per number.

SpaceO(1)Nothing beyond the output list itself.

Learn the idea: Bit Manipulation Introduction to Dynamic Programming

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code