Short and simple solution: O(n) time, O(n) space (392ms C++)


  • 1
    J

    Consider for num > 0:

    • If num is even: countBits(num) = countBits(num/2).
    • If num is odd: countBits(num) = countBits(num/2) + 1.
    • In other words: countBits(num) = countBits(num >> 1) + (num & 1).

    Of course, implementing this with recursion would lead to a terrible runtime. Instead do it bottom up (that is, dynamic programming).

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

Log in to reply
 

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