# My java solution 10ms using dynamic programming, O(n) runtime, O(n) space complexity

• ``````public class Solution {
public int[] countBits(int num) {

if (num < 2){
return num == 0 ? new int[]{0} : new int[]{0,1};
}

int[] counts = new int[num+1]; //array to hold results

//base case
counts[0] = 0;
counts[1] = 1;

int setIndex = 2; //index will keep track of each number range. a number range starts at a power of 2 (such as 2^1)
//each particular power of 2^i, the number range will contain 2^i numbers

int iteration = 0; //keeps track the current number range being iterated over

while (setIndex < counts.length){

int currPointer = setIndex; //keep pointer to current index of the range you are iterating over

//the first half of numbers in a set will have the same value as the first half of the numbers in the previous set
for (int i = setIndex; i < setIndex/2+setIndex && i < counts.length; i++){
counts[i] = counts[i-((int)Math.pow(2, iteration))]; //gets the values of the first half of the previous range
currPointer++;
}

//the second half of numbers in a set will have the values of the numbers in the first half of the set incremented by 1
for (int j = currPointer; j <= setIndex*2-1 && j < counts.length; j++){
counts[j] = counts[j-setIndex/2] + 1;  //get the values of
currPointer++;
}

//update set index to be index of next power of 2 set
//increase the pointer of the current number range iteration
setIndex = currPointer;
iteration++;
}

return counts;

}
}``````

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