338 Counting Bits
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.
Example:
For
num = 5you should return[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).
- Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
The Idea: This is an identified sequence, (see https://oeis.org/A000120). The pattern can be recursively identified. One way it is identified is through this triangular pattern.
0,
1, <- base case
1,2,
1,2,2,3,
1,2,2,3,2,3,3,4,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
Beginning with the two base cases 0 and 1, we can identify the pattern simply copies the layer above it twice with the second half incremented by 1. The pattern grows by
2^n, but we can always return a subvector [0:num] since 2^n >= num.Complexity: O(num) time and O(log(num)) extra space.
def __countBits(self, A000120, prev, num):
"""
:param num: int
:return: List[int]
"""
if len(A000120) >= num + 1:
return A000120
else:
A000120.extend(prev)
double = [i+1 for i in prev]
A000120.extend(double)
prev.extend(double)
return self.__countBits(A000120, prev, num)
def countBits(self, num):
"""
:type num: int
:rtype: List[int]
"""
if num == 0: return [0]
elif num == 1: return [0,1]
return self.__countBits([0,1], [1], num)[0:num+1]