Blind 75.13 - Counting Bits

Counting bits.

Problem description

Taken directly from LeetCode.

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1’s in the binary representation of i.

Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 –> 0
1 –> 1
2 –> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 –> 0
1 –> 1
2 –> 10
3 –> 11
4 –> 100
5 –> 101 \

Constraints:

• 0 <= n <= 105

Follow up:

• It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
• Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

Solution type

Caching.

Solution

Coming immediately from the previous question, the first thing I’m asking my self is “why not run our previous Hamming weight algorithm on values 0 through n?”. The quick and obvious answer to that is that the Hamming weight algorithm is still \(O(\log n)\); it’s not \(O(1)\) and therefore won’t give us an \(O(n)\) solution overall.

I doubt there’s a way to get the Hamming weight in \(O(1)\), so we do NOT want to ask “what is the Hamming weight for the current index?” at every step of this algorithm. Instead, we should use some fact about how binary representations of numbers work to work from 0 up to n and fill in the Hamming weights as we go along.

Let’s write out numbers 0-15 in binary:

0
1
10
11
100
101
110
111
1000
1001
1010
1011
1100
1101
1110
1111

Notice how there’s some repetition? After 0 and 1, the next two numbers are 0 and 1 again except with a second bit set to 1. The next four numbers after that are 0, 1, 10, 11 again but with an additional third bit set to 1. Basically, we can look earlier in the array, note how many 1s there were before, and then add an extra 1 for the MSB that we are adding on this “iteration” of the algorithm.

How far back we look depends on the position of the MSB. Basically, for a given index, take the number of 1s stored at \(2^{\textrm{MSB position}}\) indices before, then add 1. That’s all you need to do. There’s a little extra logic in the solution below to track and update the MSB.

def countBits(self, n: int) -> List[int]:
    ret = [0] * (n + 1)
    MSB = 1
    for i in range(1, n + 1):
        if i == MSB * 2:
            MSB = i
        ret[i] = ret[i - MSB] + 1
    return ret

It’s a little cleaner to do something like ret[i] = ret[i / 2] + i % 2 to avoid storing this MSB variable. At the end of the day, though, it’s an insignificant difference.