Super Pow in JS


  • 0

    We are going to try to do the SuperPow exercise in JS

    In JS, numbers are represented using double-precision 64-bit format IEEE 754.
    Integers must be below Number.MAX_SAFE_INTEGER, so we must be careful to not exceed this value. And since the second argument b is said to be an extremely large positive integer, we must find a good way to compute the value incrementally

    Let's see some modulo rules we can use

    • a = b mod n => k*a = k*b mod n
    • a = b mod n and c = d mod n => a*c = b*d mod n
    • a = b mod n => a^k = b^k mod n

    So a**(b2*10**2 + b1*10 + b0) % n is: (** is the power/exponentiation operator in JS)

    • (a**(b2*10**2) * a**(b1*10) * a**(b0)) % n
    • (a**(b2*10**2) % n) * (a**(b1*10) % n) * (a**(b0) % n)
    • (((a**b2 % n)**10 % n)**10 % n) * (((a**b1 % n)**10) % n) * (a**(b0) % n)

    in short we can take modulo at every step, let's try to translate into code:

    1st attempt

    /**
     * @param {number} a
     * @param {number[]} b
     * @return {number}
     */
    var superPow = function(a, b) {
        var base = a % 1337;
        var r = 1;
        b.forEach((k, i) => {
            if (!k) return; // nothing to do
            var q = base**k % 1337;
            for (var j=0; j<b.length-1-i; j++) { // process all power of 10
                q = q**10 % 1337;
            }
            r = q*r % 1337; // multiply with previous item in b
        });
        return r;
    };
    

    It passes a few tests, but fail quite soon. Why? the values sometimes exceed Number.MAX_SAFE_INTEGER

    Let's isolate modulo 1337, so we can check when it exceeds, at the same time, let's "center" it, to minimize absolute values:

    var mod1337 = n => {
        if (Math.abs(n) > Number.MAX_SAFE_INTEGER) console.warn('!!', n);
        var v = n % 1337;
        return v > 669 ? v - 1337 : v;
    }
    

    As we are on it, let's make a quick estimation
    At worst case, a value is 669
    669**5 > Number.MAX_SAFE_INTEGER // false, good
    669**6 > Number.MAX_SAFE_INTEGER // true..

    So we have to split also the digits, when they are above 5, let's split them in any case for simplicity:

    2nd attempt

    /**
     * @param {number} a
     * @param {number[]} b
     * @return {number}
     */
    var superPow = function(a, b) {
    	var base = mod1337(a);
    	var r = 1;
    	b.forEach((k, i) => {
    		if (!k) return;
    		// split k in 2, to make sure we stay under MAX_SAFE_INTEGER
    		var u = Math.floor(k/2), v = k - u;
    		var q = mod1337(mod1337(base**u) * mod1337(base**v));
    		for (var j=0; j<b.length-1-i; j++) {
    			q = mod1337(q**5); // split 10 in 5*2
    			q = mod1337(q**2);
    		}
    		r = mod1337(q * r);
    	});
    	return (r + 1337) % 1337; // return a result in [0, 1336]
    };
    

    Now it works!


Log in to reply
 

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