# Simple Java O(n) solution using two pointers

• This uses the hint from the description about using ranges. Basically, the numbers in one range are equal to 1 plus all of the numbers in the ranges before it. If you write out the binary numbers, you can see that numbers 8-15 have the same pattern as 0-7 but with a 1 at the front.

My logic was to copy the previous values (starting at 0) until a power of 2 was hit (new range), at which point we just reset the t pointer back to 0 to begin the new range.

``````public int[] countBits(int num) {
int[] ret = new int[num+1];
ret[0] = 0;
int pow = 1;
for(int i = 1, t = 0; i <= num; i++, t++) {
if(i == pow) {
pow *= 2;
t = 0;
}
ret[i] = ret[t] + 1;
}
return ret;
}``````

• Great Solution! Thank you for sharing!

• Much easier to understand. Good job.

• My Solution:

``````public class Solution {
public int[] countBits(int num) {
int[] result = new int[num+1];
result[0] = 0;
for(int i=1;i<=num;i++){
if(i%2!=0) result[i] = result[i-1]+1;
else if(1073741824%i==0) result[i] = 1;
else result[i] = result[i/2];
}
return result;
}
}
``````

• My thought is the same as yours, but in different way:

``````public class Solution {
public int[] countBits(int num) {
//这题主要是动态规划，也就是后面的个数可以通过前面得到的计算
if (num < 1)
return new int[] {0};

int [] count = new int[num+1];
count[0] = 0;

int k = 0;

for (int i = 1; i <= num;) {
k = i;
for (int j =0; j < i; j++) {
if (k <= num) {
count[k++] = count[j] + 1;
}
}
if (k > num)
break;
i = k;

//  }
}
// ret:
return count;
}
}
``````

• Thanks for sharing! Here is my similar thought without variable t though (maybe slightly slower than yours but more concise). I assume the solution of this problem is much alike that of Gray Code.

``````    public int[] countBits(int num) {
int[] bit1s = new int[num + 1];
for (int i = 1, j = 1; i <= num; i++) {
if (i == j * 2) {
j <<= 1;
}
bit1s[i] = bit1s[i - j] + 1; // assert: i - j >= 0
}
return bit1s;
}
``````

• This technique is similar to Brent's Cycle Detection algorithm.

``````    if(i == pow) {
pow *= 2;
t = 0;
}``````

• @Alderdragon Genius~

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