Counting Bits

Problem

Approach

approach 1: the easiest way to count bits from 0 to N: for every number i, get its’ bits by calculating all the bits.
approach 2: the next way is to utilize DP. DP[i] = DP[j1] + DP[j2] + ... + DP[jn], j1 + j2 + ... + jn = i. As every number i is added by lots of j, which j is 1, 2, 4, 8, 16 and so on.
approach 3: By observing the bits of numbers from 0 to n, we can find that : first round: 0: 0 -> 0 1: 1 -> 1 second round(the number of numbers is 2^1): 2: 10 -> 1 = 0 + 1 3: 11 -> 2 = 1 + 1 third round(the number of numbers is 2^2): 4: 100 -> 1 = 0 + 1 5: 101 -> 2 = 1 + 1 6: 110 -> 2 = 0 + 1 + 1 7: 111 -> 3 = 1 + 1 + 1 forth round(the number of numbers is 2^3): 8: 1000 -> 1 = 0 + 1 9: 1001 -> 2 = 1 + 1 10: 1010 -> 2 = 0 + 1 + 1 // in every round, these numbers are updated with these rounds before self. …
approach 4: one more easier way is to use DP, too. But, the DP state is different now. DP[i] = DP[i / 2] + (i % 2). Because for these odd numbers, its’ bits is one more than the half and for these even, they are same as their half.

Code

for approach 1

None

for approach 2

class Solution {
 public int log(int n){
     return (int)(Math.log(n) / Math.log(2.0));
 }
 public int[] countBits(int num) {
     if(num == 0) {
         return new int[]{0};
     }
     if(num == 1) {
         return new int[]{0, 1};
     }
     int[] dp = new int[num + 1];
     dp[0] = 0;
     dp[1] = 1;
     dp[2] = 1;
     for(int i = 3; i <= num; i ++){
         int temp = i;
         dp[i] = 0;
         while(temp > 0){
             int log1 = log(temp);
             int log2 = (int)Math.pow(2, log1);
             dp[i] += dp[log2];
             temp -= log2;
         }
         if(dp[i] == 0) dp[i] = 1;
     }
     return dp;
 }
}

for approach 3

class Solution {
 public int[] countBits(int num) {
     int[] ans = new int[num + 1];
     if(num >= 0){
         ans[0] = 0;
     }
     if(num >= 1){
         ans[1] = 1;
     }
     int id = 2;
     while(id <= num){
         int oldId = id;
         for(int i = 0; i < oldId; i ++){
             ans[id] = ans[i] + 1;
             id ++;
             if(id > num){
                 break;
             }
         }
         if(id > num){
             break;
         }
     }
     return ans;
 }
}

for approach 4

class Solution {
 public int[] countBits(int num) {
     int[] dp = new int[num + 1];
     for(int i = 0; i <= num; i ++){
         dp[i] = dp[i / 2] + i % 2;
     }
     return dp;
 }
}