Counting bits#

Levels: level-4

Data structures: bits, array

Practice Link#

Description#

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Examples#

1Input: 2
2Output: [0,1,1]

1Input: 5
2Output: [0,1,1,2,1,2]

Follow up#

It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).

Thinking#

We do not need check the input parameter, because the question has already mentioned that the number is non negative.
How we do this? The first idea come up with is find the pattern or rules for the result. Therefore, we can get following pattern
```
1Index : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2num : 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4
```
Do you find the pattern?

Obviously, this is overlap sub problem, and we can come up the DP solution. For now, we need find the function to implement DP.

1dp[0] = 0;
2dp[1] = dp[0] + 1;
3dp[2] = dp[0] + 1;
4dp[3] = dp[1] +1;
5dp[4] = dp[0] + 1;
6dp[5] = dp[1] + 1;
7dp[6] = dp[2] + 1;
8dp[7] = dp[3] + 1;
9dp[8] = dp[0] + 1;

This is the function we get, now we need find the other pattern for the function to get the general function.

After we analyze the above function, we can get

1dp[0] = 0;
2dp[1] = dp[1-1] + 1;
3dp[2] = dp[2-2] + 1;
4dp[3] = dp[3-2] +1;
5dp[4] = dp[4-4] + 1;
6dp[5] = dp[5-4] + 1;
7dp[6] = dp[6-4] + 1;
8dp[7] = dp[7-4] + 1;
9dp[8] = dp[8-8] + 1;

Obviously, we can find the pattern for above example, so now we get the general function dp[index] = dp[index - offset] + 1;

Python Solution#

 1class Solution(object):
 2    def countBits(self, num):
 3        """
 4        :type num: int
 5        :rtype: List[int]
 6        """
 7        result = [0] * (num + 1)
 8        offset = 1
 9        for index in range(1, num + 1):
10            if (offset * 2 == index):
11                offset *= 2
12            result[index] = result[index - offset] + 1
13        return result