Super simple DP solution in JavaScript


  • 0
    D
    /**
     * @param {number} n
     * @return {number}
     */
    // NOTE: converted previous iterative DP solution to recursive DP solution
    // because previous solution gave MLE - memory limit exceeded error
    var integerReplacement = function(n) {
        
        let dp = [];
    
        return util(n);
        
        function util(n){
            
            if(n == 1){
               return 0;
            }
            
            if(dp[n]){
               return dp[n];
            }
            
            if(n % 2 == 0){
               dp[n] = util(n/2) + 1;
            }
            else {
                let a = util(n-1) + 1;
                let b = util((n+1)/2) + 2;
                
                dp[n] = Math.min(a,b);
            }
            
            return dp[n];
            
        }
        
    };
    
    

Log in to reply
 

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