###### tags: `leetcode`
# LeetCode #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 1:

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

Example 2:

Input: 5
Output: [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.

## Python, for-loop and count ones, t=O(nlgn),s=O(1)

class Solution:
    def countBits(self, num: int) -> List[int]:
        
        def countOnes(x):
            count = 0
            while x != 0:
                count += 1
                x = x & (x-1)
            return count
        
        ans = []
        for i in range(num + 1):
            ans.append(countOnes(i))
        return ans

## Python, ???
### my thinking
It is easy to observe an pattern in the sequence.
Let $f$ be the function.
Let $.+$ be element-wise addition.

f(0) = [0]
f(1) = [0,1]             = [f(0), f(0).+1]
f(3) = [0,1,1,2]         = [f(1), f(1).+1]
f(7) = [0,1,1,2,1,2,2,3] = [f(3), f(3).+1]

### try on 2^N

def fun(x):  # assume x is power of 2
    if x == 0:
        return [0]
    else:
        a = fun((x+1)/2-1)  #　int 
        for i in range(len(a)):
            a.append(a[i] + 1)
        return a
    
print(fun(3)) 

#### to improve
How to add an integer to each element in a list? =
https://stackoverflow.com/questions/9304408/how-to-add-an-integer-to-each-element-in-a-list

new_list = [x+1 for x in my_list]