Suppose we calculated answers for the numbers till X. Now, we want to compute answer for the number X. By removing any bit of X we will decrease the number, i.e. we can use answers which we've already calculated. One option to find any set bit of X is to track the most significant bit.

More formally we come to recurrence relation as below

bitcounts(i) = bitcounts(i-(2^mostSignificantBit)) + 1

```
public class Solution {
public int[] countBits(int num) {
int bits[] = new int[num+1];
int powerTwo = 1;
int prevPos = 0;
for (int i=1; i<=num; i++) {
bits[i] = bits[prevPos]+1;
prevPos++;
if (prevPos==powerTwo) {
prevPos = 0;
powerTwo = powerTwo*2;
}
}
return bits;
}
}
```