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


  • 6
    E

    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.


  • 0
    Y

    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;
    }

Log in to reply
 

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