5ms Java solution O(n) space and time, easy to understand

• The hint actually has revealed enough.
Just follow the fact:
Any integer's binary presentation is highest 1 bit plus what is remained. For example: `10101011 = 10000000 + 101011`, so if we know the bits of 101011, we know the bits of 10101011.

``````public class Solution {
public int[] countBits(int num) {
if(num <= 0)
return new int[1];
int[] dp = new int[num + 1];
dp[1] = 1;
int power2 = 2, idx = 2;
while(idx <= num){
if(idx == power2){
power2 *= 2;
dp[idx] = 1;
idx++;
}else{
dp[idx] = 1 + dp[idx - power2/2];
idx++;
}
}
return dp;
}
}
``````

in order to get really one pass solution, I keep track of next 2^i to make sure current number idx is between 2^(i-1) and 2^i.

• Same solution with more clear code snippet.
For example, 7 = 4+3; then dp[7] = dp[4] + dp[3];

``````  public int[] countBits(int num) {
if(num <=0) return new int[1];
int[] dp = new int[num+1];
dp[1] = 1;
int idx =2;
int pow = 1;
while(idx <= num){
if(idx == pow *2){
pow = pow*2;
dp[idx++] = 1;
}else{
dp[idx] = dp[pow] + dp[idx-pow];
idx++;
}
}
return dp;
}``````

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