Largest Palindrome Product

hard math

Problem

Find the largest palindrome made from the product of two n-digit numbers, modulo 1337.

Inputn = 2

Output987

987 = 99 × 91 (mod 1337 = 987).

def largest_palindrome(n):
    if n == 1: return 9
    upper = 10**n - 1
    lower = 10**(n - 1)
    for left in range(upper, lower - 1, -1):
        s = str(left)
        palindrome = int(s + s[::-1])
        x = upper
        while x * x >= palindrome:
            if palindrome % x == 0:
                return palindrome % 1337
            x -= 1
    return -1

function largestPalindrome(n) {
  if (n === 1) return 9;
  const upper = 10 ** n - 1;
  const lower = 10 ** (n - 1);
  for (let left = upper; left >= lower; left--) {
    const s = String(left);
    const palindrome = BigInt(s + s.split("").reverse().join(""));
    let x = BigInt(upper);
    while (x * x >= palindrome) {
      if (palindrome % x === 0n) return Number(palindrome % 1337n);
      x--;
    }
  }
  return -1;
}

class Solution {
    public int largestPalindrome(int n) {
        if (n == 1) return 9;
        long upper = (long) Math.pow(10, n) - 1;
        long lower = (long) Math.pow(10, n - 1);
        for (long left = upper; left >= lower; left--) {
            String s = String.valueOf(left);
            long palindrome = Long.parseLong(s + new StringBuilder(s).reverse());
            for (long x = upper; x * x >= palindrome; x--) {
                if (palindrome % x == 0) return (int) (palindrome % 1337);
            }
        }
        return -1;
    }
}

int largestPalindrome(int n) {
    if (n == 1) return 9;
    long upper = (long) pow(10, n) - 1;
    long lower = (long) pow(10, n - 1);
    for (long left = upper; left >= lower; left--) {
        string s = to_string(left);
        string r = s; reverse(r.begin(), r.end());
        long palindrome = stol(s + r);
        for (long x = upper; x * x >= palindrome; x--) {
            if (palindrome % x == 0) return (int) (palindrome % 1337);
        }
    }
    return -1;
}

Explanation

We want the biggest palindrome that is a product of two n-digit numbers. The smart move is to generate palindromes directly from largest to smallest and stop at the first one that can actually be factored that way, rather than multiplying every pair of numbers.

A palindrome of length 2n is fully determined by its upper half: we just mirror it. So we loop left from the largest n-digit number down, and build palindrome = int(s + reverse(s)). Because we count down, the first valid palindrome we find is the largest.

To check if a palindrome is a valid product, we try dividing it by n-digit numbers x starting from the top. If palindrome % x == 0 and the quotient is also n digits, it works. The loop condition x * x >= palindrome stops once x would be smaller than the other factor, avoiding redundant checks.

Example: for n = 2 the answer comes from 9009 = 99 * 91, and the problem asks for it modulo 1337, giving 987.

The n = 1 case is hard-coded as 9 (= 3 × 3) because the two-digit-mirror construction does not apply to a single-digit palindrome.

Time: O(100^n) Space: O(1)