If you look at the binary table progression it's evident that at each power of two, the number of ones progression is equal to the number of ones starting from 0 up to the current index plus one (*check out the Binary Progression below)*. Therefore, our algorithm will iterate starting at 1, and keep building up our bit count array by 2x every progression until we reach our expected num.

```
Binary Progression
0 0
1 1 <- index(0)+1
2 10 <- index(0)+1
3 11 <- index(1)+1
4 100 <- index(0)+1
5 101 <- index(1)+1
6 110 <- index(2)+1
7 111 <- index(3)+1
8 1000 <- index(0)+1
```

```
public int[] CountBits(int num) {
int[] bitCount = new int[num+1];
for(int i=1; i<=num; i *= 2) {
for(int j=0; j<i && j+i<=num; j++) {
bitCount[i+j] = 1+bitCount[j];
}
}
return bitCount;
}
```