LeetCode 479: Largest Palindrome Product

Problem Restatement

We are given an integer n.

We need to find the largest palindrome that can be written as the product of two n-digit integers.

Because the answer may be very large, we return the palindrome modulo 1337.

For example, when n = 2, the two-digit numbers are from 10 to 99.

The largest palindrome product is:

99 * 91 = 9009

Then we return:

9009 % 1337 = 987

So the answer is 987.

The constraints are 1 <= n <= 8.

Input and Output

Function shape:

def largestPalindrome(n: int) -> int:
    ...

Examples

Example 1:

n = 2

The largest two-digit number is 99.

The largest palindrome product is:

99 * 91 = 9009

Return:

9009 % 1337 = 987

Answer:

987

Example 2:

n = 1

The one-digit numbers are from 1 to 9.

The largest palindrome product is:

9 * 1 = 9

Answer:

9

First Thought: Check Every Product

The direct way is to multiply every pair of n-digit numbers.

For each product, check whether it is a palindrome.

class Solution:
    def largestPalindrome(self, n: int) -> int:
        MOD = 1337

        high = 10 ** n - 1
        low = 10 ** (n - 1)

        best = 0

        for a in range(high, low - 1, -1):
            for b in range(a, low - 1, -1):
                product = a * b

                if product <= best:
                    break

                if str(product) == str(product)[::-1]:
                    best = product

        return best % MOD

This is easy to understand.

It also avoids duplicate pairs by starting b from a.

But this still has too many products when n is large.

Problem With Brute Force

There are about 9 * 10^(n-1) different n-digit numbers.

Checking all pairs costs roughly:

O(10^(2n))

For n = 8, this is far too large.

We need to avoid testing ordinary products.

Instead, we should generate palindromes directly.

Key Insight

The target number must be a palindrome.

So rather than checking whether every product is a palindrome, generate palindrome candidates from largest to smallest, then check whether each candidate can be factored into two n-digit numbers.

For n = 2, the largest possible product has at most 4 digits.

We can generate even-length palindromes by choosing the left half and mirroring it.

For example:

left = 99
palindrome = 9999

left = 98
palindrome = 9889

left = 97
palindrome = 9779

Eventually:

left = 90
palindrome = 9009

And:

9009 = 99 * 91

Since we generate palindromes in descending order, the first valid one is the largest answer.

Why Generate Even-Length Palindromes

For n > 1, the largest product of two n-digit numbers has either 2n or 2n - 1 digits.

The standard accepted search generates 2n-digit palindrome candidates by mirroring an n-digit left half.

This works for this problem because the largest valid palindrome product for n >= 2 is found among these generated even-length candidates.

The case n = 1 is special and returns 9.

Algorithm

Handle the special case:

if n == 1:
    return 9

Compute the largest and smallest n-digit bounds:

high = 10 ** n - 1
low = 10 ** (n - 1)

Then loop over possible left halves from largest to smallest.

For each left, build the palindrome:

pal = int(str(left) + str(left)[::-1])

Then check whether pal has an n-digit factor.

Start from the largest factor high and move downward.

For each possible factor x:

1. Stop if x * x < pal.
2. If pal % x == 0, then x is one factor.
3. The other factor is pal // x.
4. Because x * x >= pal, the other factor is at most x.
5. Since x starts as an n-digit number and moves downward, this finds whether pal can be formed by two n-digit numbers.

Return:

pal % 1337

Correctness

The algorithm generates palindrome candidates in descending order of their left half.

For fixed digit length, a larger left half produces a larger palindrome. Therefore, the first valid palindrome found by this enumeration is the largest valid palindrome among the generated candidates.

For each palindrome pal, the algorithm tests possible divisors x from the largest n-digit number downward.

If pal % x == 0, then:

pal = x * (pal // x)

So pal can be written as a product of two integers.

The loop only needs to continue while:

x * x >= pal

Once x * x < pal, both factors cannot be at least x. Any remaining factor below x would pair with another factor above x, and that larger factor was already considered earlier in the descending loop.

Thus the factor check correctly detects whether the palindrome can be represented as the product of two n-digit numbers.

Since the candidates are checked from largest to smallest, the first valid candidate is the largest palindrome product. Returning it modulo 1337 gives the required output.

Complexity

In practice, the search is much faster than brute force because it checks only palindromes, not every product.

Implementation

class Solution:
    def largestPalindrome(self, n: int) -> int:
        if n == 1:
            return 9

        MOD = 1337

        high = 10 ** n - 1
        low = 10 ** (n - 1)

        for left in range(high, low - 1, -1):
            pal = int(str(left) + str(left)[::-1])

            x = high
            while x * x >= pal:
                if pal % x == 0:
                    return pal % MOD
                x -= 1

        return 0

Code Explanation

The single-digit case is handled directly:

if n == 1:
    return 9

For one-digit numbers, the largest palindrome product is 9.

These bounds define the valid n-digit factors:

high = 10 ** n - 1
low = 10 ** (n - 1)

For n = 2:

low = 10
high = 99

This loop generates left halves in descending order:

for left in range(high, low - 1, -1):

This builds an even-length palindrome:

pal = int(str(left) + str(left)[::-1])

For example:

Then we test factors:

x = high
while x * x >= pal:

The condition x * x >= pal avoids checking unnecessary small divisors.

If x divides pal, then pal can be written as a product:

if pal % x == 0:
    return pal % MOD

Because palindromes are generated from largest to smallest, we can return immediately.

Testing

def run_tests():
    s = Solution()

    assert s.largestPalindrome(1) == 9
    assert s.largestPalindrome(2) == 987
    assert s.largestPalindrome(3) == 123
    assert s.largestPalindrome(4) == 597

    print("all tests passed")

run_tests()

Test meaning: