# 3 ms O(n) time and O(1) space Java solution using DP Easy to understand and well explained

• ``````    /*
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
0	1	1	2	1	2	2	3	1	2	2	3	2	3	3	4	1
*/
/*
If we look at the series above it can be inferred that after each power of 2 (1, 2, 4,8, 16) each next
number is the power of 2 plus the difference for example 5 = (4 +1), 6 = (4 + 2), ...
so number of ones in the bit will also be equal to number of bit bit in previous power of 2
(which is 1) plus the number of ones in number generated after difference. Hence it gives clue for
solving this problem using DP. put the base cases of 0, 1, 2 and then start adding number of ones
each index by adding from previous stored results.
*/
public int[] countBits(int num) {
int[] result = new int[num+1];

/*base condition starts*/

if(num == 0) return result;
result[1] = 1;
if(num == 1) return result;
result[2] = 1;
if(num == 2) return result;

/*base condition ends*/

int count = 1, start = 2; // initialize initial counters and start value
for(int i = 3; i < num + 1 ; i++){
/* if number is power of 2*/
if(count == start){
result[i] = count = 1;
start = i;
}else{ // add the number of bits from previously calculated sequence
result[i] = result[count] + result[start];
count++;
}
}
return result;
}``````

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