Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.
Example:
For
num = 5 you should return [0,1,1,2,1,2].Let's list the some examples, left column are the numbers, the right column are the number of bits for each number.
0 0
1 1 <-- go back to 1
2 1 <-- go back to 1
3 2
4 1 <-- go back to 1
5 2
6 2
7 3
8 1 <-- go back to 1
.
.
.
16 1 <-- go back to 1
First of all, we observe for every 2^n number, the number of bits will be 1. Now we need to figure out the number of bits for each number between the 2^(n-1) and 2^n. Using function bits(int num) as example, we can see
bits(2)=1
bits(3) = bits(2) + bits(3-2)
bits(4) = 1
bits(5) = bits(4) + bits(5-4)
bits(6) = bits(4) + bits(6-4)
bits(7) = bits(4) + bits(7-4)
bits(8) = 1
Got it?
can be as short as this:
ReplyDeletepublic int[] countBits(int num) {
num++;
int[] ans = new int[num];
for (int i = 1; i < num; i++) {
ans[i] = ans[i & (i - 1)] + 1;
}
return ans;
}
how did you come up the solution? I am interested in the reasoning or the thinking steps behind the solution.
ReplyDelete