Summary of 2 solutions


  • 0

    Here is my original brute force solution

    class Solution {
    public:
        vector<int> countBits(int num) {
            vector<int> result;
            for(int i = 0; i <= num; i++) {
                result.push_back(bit_help(i));
            }
            return result;
        }
        
        int bit_help(int num) {
            int count = 0;
            while(num) {
                int last_bit = num&(-num);
                if(last_bit) {
                    count++;
                    num = num - last_bit;
                } else {
                    break;
                }
            }
            return count;
        }
    };
    

    Of course, it is rebundant. How to optimize it ?
    To optimze the solution, we need to find the recursion equation that can help us to use the previous computed solutions.

    class Solution {
    public:
        vector<int> countBits(int num) {
            vector<int> result(num + 1, 0);
            for(int i = 1; i <= num; i++) {
                result[i] = result[i - (i&(-i))] + 1;
            }
            return result;
        }
    };

Log in to reply
 

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