Largest Palindrome Product — Hard Problem & Solution

Problem statement

Given n, find the largest palindrome (a number that reads the same forwards and backwards in decimal) that can be written as the product of two n-digit integers.

The palindrome can be huge, so return it modulo 1337.

Example 1

Input: n = 2
Output: 987
Explanation: 99 × 91 = 9009, and 9009 % 1337 = 987.

Example 2

Input: n = 1
Output: 9
Explanation: 3 × 3 = 9 (or 9 × 1).

Example 3

Input: n = 3
Output: 123
Explanation: 993 × 913 = 906609, and 906609 % 1337 = 123.

Constraints

• 1 <= n <= 8

How to solve Largest Palindrome Product

Both factors of the answer sit just below 10^n. Writing them as 10^n - p and 10^n - q turns 'is the product a palindrome?' into a quadratic in p and q, which can be tested in O(1) for each value of s = p + q, scanned upward from 2.

Approach

1. If n == 1, return 9.
2. For s = 2, 3, 4, …: let upper = 10^n - s and lower = reverse(upper) (as a number).
3. p and q are the roots of t² - s·t + lower = 0; compute disc = s² - 4·lower. Skip if it is negative.
4. If disc is a perfect square, the palindrome upper·10^n + lower is a product of two n-digit numbers; return (upper mod 1337 · 10^n mod 1337 + lower) mod 1337.

Why it works

(10^n - p)(10^n - q) = (10^n - s)·10^n + pq, so if pq = reverse(10^n - s) (which is below 10^n) the product is literally the palindrome with upper half 10^n - s; conversely the perfect-square test recovers p = (s + r)/2, q = (s - r)/2 exactly. A smaller s means a larger upper half, so the first hit is the largest palindrome among products with pq < 10^n. A product with pq ≥ 10^n needs s ≥ 2·10^(n/2), and its upper half is then at most 10^n - 2·10^(n/2) + 1; the scan hits first at s = 10, 100, 340, 1000, 4336, 10000 for n = 2, 4, 5, 6, 7, 8, all below that bound, so nothing larger is skipped. For n = 3 (hit at s = 94) an exhaustive search confirms 906609 = 913 × 993 is the maximum.

Complexity

• Time — O(s* · n) — about 10^4 tiny steps for n = 8
• Space — O(1)

Pitfalls

• The plain search (palindromes downward, try every divisor) is correct but needs ~10^7 divisions for n = 8 — fine in C++, far too slow in Python.
• The palindrome for n = 8 exceeds 2^53: in JavaScript never form upper·10^n — reduce both factors modulo 1337 first.
• n = 1 is special: its answer 9 has one digit, not two.

Reference solution

Python

import math

def largestPalindrome(n: int) -> int:
    if n == 1:
        return 9
    base = 10 ** n
    for s in range(2, base):
        upper = base - s
        lower = int(str(upper)[::-1])
        disc = s * s - 4 * lower
        if disc < 0:
            continue
        r = math.isqrt(disc)
        if r * r == disc:
            return (upper * base + lower) % 1337
    return -1

JavaScript

var largestPalindrome = function(n) {
    if (n === 1) return 9;
    var base = Math.pow(10, n);
    for (var s = 2; s < base; s++) {
        var upper = base - s;
        var lower = 0, t = upper;
        while (t > 0) {
            lower = lower * 10 + (t % 10);
            t = Math.floor(t / 10);
        }
        var disc = s * s - 4 * lower;
        if (disc < 0) continue;
        var r = Math.floor(Math.sqrt(disc));
        while (r * r > disc) r--;
        while ((r + 1) * (r + 1) <= disc) r++;
        if (r * r === disc) return ((upper % 1337) * (base % 1337) + lower) % 1337;
    }
    return -1;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Number of Squareful Arrays Hard
• Permutation Sequence Hard
• 24 Game Hard
• Verbal Arithmetic Puzzle Hard
• Expression Add Operators Hard
• Transform to Chessboard Hard