Two Linear Time Solutions - Counting Bits


  • 1
    N

    Solution 1:

    vector<int> countBits(int num) {
        vector<int> dp(num+1, 0);
        for(int i = 1 ; i <= num ; i++) {
            if( i%2 == 0 ) 
                dp[i] = dp[i/2];
            else
                dp[i] = dp[i/2]+1;
        }
        return dp;
    }
    

    Solution 2:

    vector<int> countBits(int num) {
        vector<int> num_of_ones(num+1, 0);
        for(int i = 1; i <= num; ++i)
            num_of_ones[i] = num_of_ones[i&(i-1)] + 1;
        return num_of_ones;
    }

Log in to reply
 

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