Recursion with memoization


  • 0
    C
    class Solution {
    public:
        vector<int> countBits(int num) {
                vector<int> ones(num+1, 0);  //initialize to zeros  
                ones[1] = 1;
                for(int i = num; i >= 0; i--){
                    num_ones(i, ones); 
                }
                ones[0] = 0;
                return ones;
        }
        
        
    private:
        
        int num_ones(int n, vector<int>& ones){
            //check memo table, return if exists
            if(ones[n] > 0){
                return ones[n];
            }
            
            // base case 
            if(n <= 1){
                return ones[1];
            }
            
            else{
                //memoize
                ones[n] = ((n & 1) + num_ones(n >> 1, ones));
                return ones[n];
            }
        }
    };
    

Log in to reply
 

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