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.

## Solution

DP with pattern

dp[i] = dp[i - k ^ 2] + 1

```
class Solution {
func countBits(_ num: Int) -> [Int] {
var dp = [Int](repeating: 0, count: num + 1)
if num == 0 { return dp }
var offset = 1
for i in 1...num {
if i == (offset * 2) {
offset *= 2
}
dp[i] = dp[i - offset] + 1
}
return dp
}
}
```