Super Pow in JS

• 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!

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