```
We can easily notice that:
0 0
1 1
2 1 0
3 1 1
which are previous results from 0 to 1 prepended by 1, with a block size of 2.
4 1 00
5 1 01
6 1 10
7 1 11
which are previous results from 0 to 3 prepended by 1, with a block size of 4.
so all later numbers can be easily "looked up" from previous numbers, it's typical dp problem.
public class Solution {
public int[] countBits(int num) {
if (num == 0) return new int[]{0}; //special case first
int[] result = new int[num+1];
result[0]=0;
int size = 1; //block size
int count =0;
for(int i =1; i<= num;i++){
result[i] = result[i-size]+1; // find the number without leading 1, then plus 1 as current value
if(++count == size){ //if we count reached block limit
size*=2; //block size doubled
count=0; //reset count
}
}
return result;
}
}
```