Notice the pattern?

N

```
0
1 2 3
4 5 6 7
8 9 10 11 12 13 14 15 16 17
```

Number of ones

```
0
1
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
```

```
def countBits(self, num):
"""
:type num: int
:rtype: List[int]
"""
r = []
t = 2
prev = [1]
while t <= (num<<1):
t = t << 1
r += prev
prev = prev + [n+1 for n in prev]
return [0] + r[0:num]
```

Assuming list concatenation and sum one to a list is made in parallel, then complexity will be O(log(n))