Largest Palindrome Product

Hard
1311.

Largest Palindrome Product

Largest Palindrome Product is a hard coding problem on math and enumeration, asked in Google and Yahoo interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var largestPalindrome = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Largest Palindrome Product — Solution in Python, Java & C++

Largest Palindrome Product solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Largest Palindrome Product is a hard coding problem on math and enumeration, asked in Google and Yahoo interviews.

  • Difficulty: Hard
  • Topics: Math, Enumeration
  • Asked at: Google, Yahoo
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

Hints for Largest Palindrome Product

  1. Hint 1

    For n ≥ 2 the answer has 2n digits, so it is fixed by its upper half — try upper halves from the largest down.

  2. Hint 2

    Write the factors as 10^n - p and 10^n - q. Their product is (10^n - (p + q))·10^n + p·q, which reads as 'upper half 10^n - s, lower half p·q' when p·q < 10^n, with s = p + q.

  3. Hint 3

    For each s = 2, 3, …, the lower half must be L = reverse(10^n - s); integers p, q with sum s and product L exist exactly when s² - 4L is a perfect square.

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

Java

public static int largestPalindrome(int n) {
    if (n == 1) return 9;
    long base = 1;
    for (int i = 0; i < n; i++) base *= 10;
    for (long s = 2; s < base; s++) {
        long upper = base - s;
        long lower = 0, t = upper;
        while (t > 0) {
            lower = lower * 10 + t % 10;
            t /= 10;
        }
        long disc = s * s - 4 * lower;
        if (disc < 0) continue;
        long r = (long) Math.sqrt((double) disc);
        while (r * r > disc) r--;
        while ((r + 1) * (r + 1) <= disc) r++;
        if (r * r == disc) return (int) ((upper * base + lower) % 1337);
    }
    return -1;
}

C++

int largestPalindrome(int n) {
    if (n == 1) return 9;
    long long base = 1;
    for (int i = 0; i < n; i++) base *= 10;
    for (long long s = 2; s < base; s++) {
        long long upper = base - s;
        long long lower = 0, t = upper;
        while (t > 0) {
            lower = lower * 10 + t % 10;
            t /= 10;
        }
        long long disc = s * s - 4 * lower;
        if (disc < 0) continue;
        long long r = (long long) sqrt((double) disc);
        while (r * r > disc) r--;
        while ((r + 1) * (r + 1) <= disc) r++;
        if (r * r == disc) return (int) ((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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue