```
/*
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1
*/
/*
If we look at the series above it can be inferred that after each power of 2 (1, 2, 4,8, 16) each next
number is the power of 2 plus the difference for example 5 = (4 +1), 6 = (4 + 2), ...
so number of ones in the bit will also be equal to number of bit bit in previous power of 2
(which is 1) plus the number of ones in number generated after difference. Hence it gives clue for
solving this problem using DP. put the base cases of 0, 1, 2 and then start adding number of ones
each index by adding from previous stored results.
*/
public int[] countBits(int num) {
int[] result = new int[num+1];
/*base condition starts*/
if(num == 0) return result;
result[1] = 1;
if(num == 1) return result;
result[2] = 1;
if(num == 2) return result;
/*base condition ends*/
int count = 1, start = 2; // initialize initial counters and start value
for(int i = 3; i < num + 1 ; i++){
/* if number is power of 2*/
if(count == start){
result[i] = count = 1;
start = i;
}else{ // add the number of bits from previously calculated sequence
result[i] = result[count] + result[start];
count++;
}
}
return result;
}
```