# Java 6ms 17lines O(n) time and space DP solution very easy to understand

• ``````public int[] countBits(int num) {
if (num == 0) {
return new int[] { 0 };
}
if (num == 1) {
return new int[] { 0, 1 };
}
int result[]=new int[num+1];
result[0]=0;
result[1]=1;
for (int i = 2; i <=num; i++) {
if (i%2==0) {
result[i]=result[i/2];
}else {
result[i]=result[i/2]+1;
}
}
return result;
}``````

• java timing calculation is wrong @LC.

• yes, it tooks 8ms when I commited my answer again.But the method I used is very easy to understand

• no offense, I find out that for all java solutions @LC, the timing is extremely good compare to c/c++ solutions, one may get the false impression that java is fastest. take this problem as example, c/c++ solutions with same algorithm took at least 120 ms.

• Can someone explain this part ?
if (i%2==0) {
result[i]=result[i/2];
}else {
result[i]=result[i/2]+1;
}

• if a number i%2==0, the bit 1 number of i must be equal to the the bit 1 number of i/2, because the i can be regard as i/2 rotating the bits once to the left. And the result[i]=result[i/2]+1, you can take some case as examples to find out the rule.

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