JavaScript solution (188ms)


  • 0
    N
    var compute_until_power = 2;
    
    // A cache class to use as a Map<number_string, number>
    var Cache = {};
    
    Cache.get = function(n) {
        return cache[n + ''];
    };
    
    Cache.set = function(n,res) {
        cache[n + ''] = res;
    };
    
    Cache.has = function(n) {
        return cache[n + ''] != null;
    };
    
    /** 
     * Simple merge function
     * Similar to merge(mergesort(..), mergesort(..))
     */
    var merge = function(x,y,z) {
        return x*y*z;
    };
    
    // a recursive function that does most of the work
    var myPowHelper = function(x,n) {
        if (n < compute_until_power) {
            if (!cache.has(n)) {
                var i;
                var res = 1;
                for (i = 0; i < n; i += 1) {
                    res *= x;
                }
    
                cache.set(n, res);
            }
    
            return cache.get(n);
        }
    
        if (!cache.has(n)) {
            var floored = Math.floor(n/2);
            var remainder = n % 2;
            console.log(floored, remainder)
            var res = merge(
                cache.get(floored) || myPowHelper(x,floored), 
                cache.get(floored) || myPowHelper(x,floored), 
                cache.get(remainder) || myPowHelper(x,remainder));
    
            cache.set(n, res);
        }
    
        return cache.get(n);
    };
    
    // make it global to make it easy
    var cache = null;
    
    /**
     * @param {number} x
     * @param {number} n
     * @return {number}
     */
    var myPow = function(x, n) {
        cache = Object.create(Cache);
        var abs_n = Math.abs(n);
        var res = myPowHelper(x,abs_n);
        cache = null;
        return (n < 0) ? 1/res : res;
    };
    
    
    // 3 ^ 6
    // (3 * 3 * 3) * (3 * 3 * 3)
    // 3 * 3 * 3   *  3 * 3 * 3

Log in to reply
 

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