# Share my 3ms JAVA Solution with explanation

• Solution 1:

As we can see:
A[1] = A[1 - 1] + 1; --> 1 - 2^0
A[2] = A[2 - 2] + 1; --> 2 - 2^1
A[3] = A[3 - 2] + 1; --> 2 - 2^1
A[4] = A[4 - 4] + 1; --> 2 - 2^2
A[5] = A[5 - 4] + 1; ...
A[6] = A[6 - 4] + 1; ...
A[7] = A[7 - 4] + 1; ...

That is because the difference between 0 and 1 is the most significant bit.
The difference between 0 and 2 is the most significant bit, so are 1 and 3, 0 and 4, 1 and 5, 2 and 6, 3 and 7... and so on so forth.
So we first set a offset = 2, and when i < offset, A[i] = A[i - offset / 2] + 1.
And update offset *= 2 when i >= offset.

``````public class Solution {
public int[] countBits(int num) {
int[] ret = new int[num + 1];
ret[0] = 0;
int offset = 2;
for(int i = 1; i <= num;i++){
if(i >= offset) offset *= 2;
ret[i] = ret[i - offset / 2] + 1;
}
return ret;
}
}
``````

Solution 2:
However, a more simple solution will be focusing on the least significant bit.

0 -> 0 A[0] = 0
1 -> 1 A[1] = 1
2 -> 10 A[2] = 1
3 -> 11 A[3] = 2
4 -> 100 A[4] = 1
5 -> 101 A[5] = 2
6 -> 110 A[6] = 2
7 -> 111 A[7] = 3

As we can see:
'100' >> 1 ==> '10' 4 & 1 = 0. So, A[4] = A[4 >> 1] + 4 & 1.
'111' >> 1 ==> '11' 7 & 1 = 1. So, A[7] = A[7 >> 1] + 7 & 1.

``````public class Solution {
public int[] countBits(int num) {
int[] ret = new int[num + 1];
ret[0] = 0;
int offset = 2;
for(int i = 1; i <= num;i++){
ret[i] = ret[i >>> 1] + (i & 1);
}
return ret;
}
}
``````

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