## let's start withfor example :

0 -- 0

1 -- 1

2 -- 10

3 -- 11

4 -- 1 00

5 -- 1 01

6 -- 1 10

7 -- 1 11

## So:

count of 1 in 1 is first1 + count of 1 in 0 (1%1)

count of 1 in 2 is first1 + count of 1 in 1 (2%2)

count of 1 in 3 is first1 + count of 1 in 2 (3%2)

count of 1 in 4 is first1 + count of 1 in 0 (4%4)

count of 1 in 5 is first1 + count of 1 in 1 (5%4)

count of 1 in 6 is first1 + count of 1 in 2 (6%4)

count of 1 in 7 is first1 + count of 1 in 3 (7%4)

## In summary :

count of 1 in n is first1 + count of 1 in n%base (base is 1,2,4,8,16...)

```
vector<int> countBits(int num) {
vector<int> res;
res.push_back(0);
if(num == 0) return res;
int base = 1 , count = 0;
for(int i=1 ; i<=num ; i++){
res.push_back(1 + res[i%base]);
if(++count==base){
base *= 2;
count = 0;
}
}
return res;
}
```