Every x=pow(2,n) where n>=1, count of 1 becomes 1. Number of ones then repeats the pattern from 0 to x-1 until x*2.

0000 --> 0

0001

0010 --> 2

0011

0100 --->4

0101

0110

0111

1000 --->8

```
vector<int> countBits(int num) {
vector<int>ones(num+1);
if(num>=0)ones[0] = 0;
if(num>=1)ones[1] = 1;
int power = 1;
for(int i=2; i<=num; i*=2){
int j=i;
int curr = 0; //start from 0
while(j<i*2 && j<=num){
ones[j] = 1 + ones[curr];
j++;
curr++;
}
}
return ones;
}
```