479. Largest Palindrome Product

Description

Given an integer n, return the largest palindromic integer that can be represented as the product of two n-digits integers. Since the answer can be very large, return it modulo 1337.

 

Example 1:

Input: n = 2
Output: 987
Explanation: 99 x 91 = 9009, 9009 % 1337 = 987

Example 2:

Input: n = 1
Output: 9

 

Constraints:

• 1 <= n <= 8

 

Solutions

Solution: Math

• Time complexity: O(10ⁿ)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
const largestPalindrome = function (n) {
  const MODULO = 1337n;
  const maximum = BigInt(10 ** n - 1);
  const minimum = BigInt(10 ** (n - 1));

  for (let num = maximum; num >= minimum; num -= 1n) {
    const str = `${num}`;
    let palindrome = str;

    for (let index = str.length - 1; index >= 0; index--) {
      palindrome += str[index];
    }
    palindrome = BigInt(palindrome);

    for (let current = maximum; current ** 2n > palindrome; current -= 1n) {
      if (palindrome % current) continue;
      return palindrome % MODULO;
    }
  }
  return 9;
};