Why does this "to the power of" Javascript Algorithm Fail with big Numbers?

Question

Question

Find the last k digits of the number nn. It is guaranteed that the length of number nn is not less than k.

Example
For n = 5, k = 3, the result should be "125"

5^5 = 3125, last 3 digits is "125"

Input / Output
[input] integer n

1 ≤ N ≤ 10^9

[input] integer k

1 ≤ k ≤ 9

[output] a string

string of length k ---> last k digits of n^n

My Code

function n2n(n, k) {
  
  let a = Math.pow(n, n);
  let b = Array.from(a.toString()).map(Number);
  return b.slice((b.length-k),).join('');
}

console.log(n2n(5, 25));
console.log(n2n(5, 3));
console.log(n2n(1, 1));
console.log(n2n(5,4));
console.log(n2n(43, 7));
console.log(n2n(999, 9));

This code seems to work for the smaller numbers, but then fails with big numbers.

My theory is that it is because when the number gets really big it is no longer a typical number but becomes 5345354+e9325 or something like that.

Do you agree that my code works? Is there a way to prevent certain numbers bing processes as NaN.

The console logs in my code provides:

3125
125
1
3125
268NaNNaN70
NaN

Answer 1

You should convert the number to BigInt to prevent the result is too big that causes precision loss:

function n2n(n, k) {
  let a = BigInt(n) ** BigInt(n);
  let b = Array.from(a.toString()).map(Number);
  return b.slice((b.length-k),).join('');
}

console.log(n2n(5, 25));
console.log(n2n(5, 3));
console.log(n2n(1, 1));
console.log(n2n(5, 4));
console.log(n2n(43, 7));
console.log(n2n(999, 9));

Answer 2

Others suggested bruteforce solutions with BigInt yet its not suitable for this problem, on largest n = 10^9 the number n^n is simply too large to fit in memory.

Instead this problem can be solved with modular arithmetics:

• Notice that getting some number modulo 10^k gives k last digits of that number

• So now we need to find n^n mod 10^k which is a very well known problem

• Instead of using Math.pow() we can implement our own pow that uses modular arithmetic

• Something like that: (this algorithm is known as binary exponentiation if it's unclear whats happening you can look it up online)

function powMod(n, power, mod) {
  if( power == 0) return 1 % mod;
  if( power %2 == 1) return BigInt(n) * BigInt(powMod(n, power-1, mod)) % mod;
  return powMod(BigInt(n)*BigInt(n) % mod, power/2, mod);
}

• Now the problem can be solved just by outputting powMod(n, n, 10 ** k)

Answer 3

By using BigInt, you could take a subset of digits for getting a wanted reuslt with number types.

This approach takes for every multiplication only the last (significant) digits for the next multiplication. The result works as long as a multiplication is possible with the wanted value.

function n2n(n, k) {
  const bigN = BigInt(n);

  let i = n,
      p = '1';

  while (i--) p = (BigInt(p) * bigN).toString().slice(-k);
  return p;
}

console.log(n2n(5, 25));
console.log(n2n(5, 3));
console.log(n2n(1, 1));
console.log(n2n(5, 4));
console.log(n2n(43, 7));
console.log(n2n(999, 9));

Answer 4

You need to use BigInt, which can be done by calling BigInt(n).

Furthermore, you can use .substr( <negative value X> ) to get the last X characters from a string.

Here's how:

function n2n(n, k) {  
  let a = BigInt(n) ** BigInt(n);
  return a.toString().substr(-k);
}

console.log(n2n(5, 25));
console.log(n2n(5, 3));
console.log(n2n(1, 1));
console.log(n2n(5, 4));
console.log(n2n(43, 7));
console.log(n2n(999, 9));
console.log(n2n(999, 19));
console.log(n2n(999, 29));
console.log(n2n(999, 39));
console.log(n2n(999, 99999999));

Also -> I previously created an answer related to all this that could provide some more background: https://stackoverflow.com/a/53518106/1220550

Answer 5

In the function, you typed Math.pow(n, n) instead of Math.pow(n, k).

Here's the old code:

function n2n(n, k) {
  
  let a = Math.pow(n, n);
  let b = Array.from(a.toString()).map(Number);
  return b.slice((b.length-k),).join('');
}

console.log(n2n(5, 25));
console.log(n2n(5, 3));
console.log(n2n(1, 1));
console.log(n2n(5,4));
console.log(n2n(43, 7));
console.log(n2n(999, 9));

And here's the new code:

function n2n(n, k) {
  
  let a = Math.pow(n, k);
  let b = Array.from(a.toString()).map(Number);
  return b.slice((b.length-k),).join('');
}

console.log(n2n(5, 25));
console.log(n2n(5, 3));
console.log(n2n(1, 1));
console.log(n2n(5,4));
console.log(n2n(43, 7));
console.log(n2n(999, 9));

Make sure you run the code to see the difference.