Memoization Example

memoization-example.js

const fs = require("fs");

// "4\n1\n2\n5\n3"
const input = fs.readFileSync(0).toString();

// [4, 1, 2, 5, 3]
const lines = input.split("\n").map((n) => parseInt(n, 10));

const T = parseInt(lines[0], 10);

// 2
// 2 * 2 - 1

// 5
// 5  *   4    *    3    *    2   *   1
// factorial(5) = 5 * factorial(4) = 5 * 4 * factorial(3)...
// factorial(N) = N * factorial(N - 1)
// factorial = 5 * factorial
// 5 * (5 - 1) * (5 - 2) * (5 - 3) * (5 - 4)

const memoize = {};

const calcFactorial = (N) => {
  if (N <= BigInt(1)) {
    return BigInt(1);
  }
  if (memoize[N]) {
    return memoize[N];
  }
  const F = N * calcFactorial(N - BigInt(1));
  memoize[N] = F;
  return F;
};

for (let t = 1; t <= T; t += 1) {
  const N = BigInt(lines[t]);
  const factorial = calcFactorial(N);

  console.log(`${factorial}`);
}