Contents

# Problem

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

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

## example 2

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

• 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

## Dynamic

Main idea - dynamic programming :

Create resulting array `k` with len `num`. Set solution ofr `0` and `1`.

Create variablem where we will save next pow of 2 -> `cmp`. Init with value == 2. Walk throw resulting array and write to `idx` position value `k[idx-cmp/2]+1`.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 `````` ``````func countBits(num int) []int { k := make([]int,num+1) k[0] = 0 if num == 0 { return k } cmp:=1 for idx:=1; idx<=num; idx++ { if idx == 1 { k[1] = 1 cmp = 2 continue } if cmp == idx { cmp *=2 } k[idx] = k[idx-cmp/2]+1 } return k } ``````