# 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 = 5`you 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.

```python
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]
```