Java DP solution, easy to understand

• ``````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;
}
}``````

• ``````nice one thank you. I came up with shorter version of it using your

public int[] countBits(int num) {
int[] counts = new int[num + 1];
counts[0] = 0;
int size = 1;
for (int i = 1; i <= num; i++) {
counts[i] = counts[i - size] + 1;
if ((i & (i + 1)) == 0) {
size = size << 1;
}
}
return counts;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.