```
This solution uses DP as previous calculated values of array elements are used to calculate next values.
Basically there are two cases which can be intuitively figured out once sequence of few numbers is written in their bit representation.
Eg:
0 -> 000
1 -> 001
2 -> 010
3 -> 011
4 -> 100
5 -> 101
6 -> 110
7 -> 111
We can deduce from above example that there are only two cases two handle, which are:
1) If number is power of 2, it can be represented by only single 1.(numbers 1, 2, 4 in the example).
2) Other numbers can be found by adding 1 to value stored in result[i - lastPowerOfTwo], where i is the current element.
This case is highly intuitive as i can be formed by adding lastPowerOfTwo (having single 1 in binary representation) to the remaining value: i - lastPowerOfTwo.
In the example result[5] can be formed by adding 1 + resu1t[5 - 4]. Therefore, result[5] = 2
public int[] countBits(int num) {
int result[] = new int[num + 1];
int lastPowerOfTwo = 0;
int curPowerValue = 0;
for (int i = 1; i <= num; i++) {
// check if current number is power of 2
if (Math.pow(2, curPowerValue) == i) {
result[i] = 1;
lastPowerOfTwo = i;
curPowerValue++;
} else {
result[i] = 1 + result[i - lastPowerOfTwo];
}
}
return result;
}
```