```
public int[] countBits(int num) {
int[] result = new int[num+1];
if(num > 0) result[1] = 1;
if(num > 1) result[2] = 1;
if(num > 2) result[3] = 2;
int prev = 2, count = 0, round = 0;
for(int i=4; i<=num; i++) {
result[i] = result[prev+count]+round;
count++;
if(count == prev) round = 1;
if(count == prev * 2) {
round = 0;
count = 0;
prev = i - 2 * prev + 1;
}
}
return result;
}
```

**main idea**

index: 00 01 | 02 03 | 04 05 06 07 | 08 09 10 11 12 13 14 15

value: 00 01 | 01 02 | 01 02 02 03 | 01 02 02 03 02 03 03 04

From index 4, we can divide array into multiple groups, each group has 4, 8, 16, 32 ... elements; each group can also divide into two parts, values in the first part is exactly the same as the previous group, and values in the second part is the values of the first part **plus 1**.