#479

Hard

LeetCode Problem Workspace

Largest Palindrome Product

Find the largest palindromic number from the product of two n-digit integers using math and enumeration efficiently.

Problem Statement

Given an integer n, determine the largest palindromic integer that results from multiplying any two n-digit numbers. Because the result can be very large, return it modulo 1337 to prevent overflow and simplify computation.

For example, if n = 2, the largest palindrome from two 2-digit numbers is 9009, which modulo 1337 yields 987. Implement a solution that handles n from 1 up to 8, ensuring correctness and efficiency.

Examples

Example 1

Input: n = 2

Output: 987

99 x 91 = 9009, 9009 % 1337 = 987

Example 2

Input: n = 1

Output: 9

Example details omitted.

Constraints

1 <= n <= 8

Solution Approach

Generate Palindrome Candidates

Start by constructing potential palindromes from the largest possible products. Use mathematical properties to generate palindromes efficiently in descending order to avoid unnecessary checks.

Factor Verification

For each candidate palindrome, enumerate potential n-digit factors. Check if the palindrome can be exactly divided by an n-digit integer and whether the corresponding quotient is also n digits. This confirms valid factor pairs.

Modulo Operation and Early Exit

Once a valid palindrome is found, return it modulo 1337. Stop enumeration early to prevent redundant computation, leveraging the fact that larger palindromes are checked first.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on generating palindrome candidates and verifying factor pairs, roughly O(10^n) in the worst case. Space complexity is minimal, mainly storing current palindrome candidates and temporary variables.

What Interviewers Usually Probe

Expect efficient palindrome generation without checking all products.
Look for correct handling of modulo 1337 to avoid integer overflow.
Check understanding of factor enumeration and early termination strategies.

Common Pitfalls or Variants

Common pitfalls

Checking every product of n-digit numbers instead of generating palindrome candidates first.
Forgetting to verify that both factors are n-digit integers.
Neglecting modulo 1337, causing incorrect results for large n.

Follow-up variants

Find the smallest palindrome from two n-digit numbers instead of the largest.
Return the largest palindrome without modulo constraints.
Compute the largest palindrome from three n-digit numbers using similar enumeration.

FAQ

What is the largest palindrome product problem about?

It asks for the maximum palindrome formed by multiplying two n-digit integers, returned modulo 1337.

Why is modulo 1337 used in Largest Palindrome Product?

Modulo 1337 prevents integer overflow and keeps the output manageable while maintaining correctness.

Can I check all products of n-digit numbers?

Brute force is inefficient; generating palindromes in descending order and verifying factors is much faster.

How do math and enumeration help in this problem?

Math generates palindrome candidates efficiently while enumeration verifies valid n-digit factors, combining speed and correctness.

What are common mistakes solving Largest Palindrome Product?

Typical errors include checking every product, ignoring n-digit constraints on factors, and forgetting modulo 1337 calculations.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def largestPalindrome(self, n: int) -> int:
        mx = 10**n - 1
        for a in range(mx, mx // 10, -1):
            b = x = a
            while b:
                x = x * 10 + b % 10
                b //= 10
            t = mx
            while t * t >= x:
                if x % t == 0:
                    return x % 1337
                t -= 1
        return 9

Continue Practicing

#204 count primes #829 consecutive numbers sum #869 reordered power of 2