LeetCode 479: Largest Palindrome Product Solution in Python – A Step-by-Step Guide

What Is LeetCode 479: Largest Palindrome Product?

In LeetCode 479: Largest Palindrome Product, you’re given an integer n, representing the number of digits in two numbers, and your task is to find the largest palindrome that can be formed by multiplying two n-digit numbers, returning the result modulo 1337. A palindrome reads the same forwards and backwards (e.g., 12321). For example, with n = 2, the largest is 9009 (99 * 91), and 9009 % 1337 = 911. It’s like finding the grandest mirrored number within a digit limit, then sealing it with a modulo twist.

Problem Statement

• Input: n (int)—number of digits in each factor.
• Output: int—largest palindrome product modulo 1337.
• Rules:
• Formed by product of two n-digit numbers (10^(n-1) to 10^n - 1).
• Must be a palindrome.
• Return result % 1337.

Constraints

• 1 <= n <= 8.

Examples to Get Us Started

• Input: n = 2
• Output: 911 (Largest: 9009 = 99 * 91, 9009 % 1337 = 911).
• Input: n = 1
• Output: 9 (Largest: 9 = 9 * 1, 9 % 1337 = 9).
• Input: n = 3
• Output: 123 (Largest: 906609 = 993 * 913, 906609 % 1337 = 123).

Understanding the Problem: Crafting the Mirror

To solve LeetCode 479: Largest Palindrome Product in Python, we need to find the largest palindrome that’s a product of two n-digit numbers, then apply modulo 1337. A naive approach—testing all pairs—could be O(10^(2n)), infeasible for n = 8 (10^16 operations). The key? Construct palindromes from the largest possible downwards and verify factors efficiently using math. We’ll explore:

• Best Solution (Mathematical Construction with Reverse Digit Manipulation): O(10^n) time, O(1) space—fast and optimal.
• Alternative Solution (Brute Force Enumeration): O(10^(2n)) time, O(1) space—simple but slow.

Let’s dive into the mathematical solution—it’s the wizard’s palindrome potion we need.

Best Solution: Mathematical Construction with Reverse Digit Manipulation

Why This Is the Best Solution

The mathematical construction with reverse digit manipulation is the top pick because it’s O(10^n) time and O(1) space, efficiently finding the largest palindrome by generating candidates from the highest possible n-digit number and checking for valid n-digit factors, avoiding exhaustive pair searches. It constructs palindromes by mirroring the left half and uses modular arithmetic for efficiency. It’s like brewing a palindrome potion by starting with the grandest mirror and testing its ingredients—ingenious and swift!

How It Works

Here’s the strategy:

• Step 1: For n-digit numbers, max = 10^n - 1, min = 10^(n-1).
• Step 2: Construct palindrome:
• Left half = max (e.g., 99 for n=2).
• Right half = reverse(left), adjust length.
• Palindrome = left * 10^n + reverse(left).
• Step 3: Decrease left half, check factors:
• For p = palindrome, find if p = a * b, a, b in [min, max].
• Use upper = p // min, check range.
• Step 4: Return p % 1337 when found.
• Why It Works:
• Largest palindrome comes from largest left half.
• Factor check ensures n-digit product.

Step-by-Step Example

Example: n = 2

• Range: 10 to 99.
• Max Left: 99.
• Palindrome: 99 * 10^2 + 99 = 9999.
• Factors: 9999 = 111 * 90, 111 > 99, try next.
• Left: 98, p = 98 * 100 + 89 = 9889.
• Factors: 9889 = 127 * 77? No, try next.
• Left: 90, p = 9009 = 99 * 91, both 2-digit, valid.
• Result: 9009 % 1337 = 911.

Example: n = 1

• Max Left: 9, p = 9.
• Factors: 9 = 9 * 1, valid.
• Result: 9 % 1337 = 9.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def largestPalindrome(self, n: int) -> int:
        if n == 1:
            return 9  # Special case

        # Step 1: Define range
        max_num = 10 ** n - 1
        min_num = 10 ** (n - 1)

        # Step 2: Start with largest left half
        left = max_num
        while left >= min_num:
            # Construct palindrome
            p = left * (10 ** n) + int(str(left)[::-1])

            # Step 3: Check factors
            upper = p // min_num
            i = min(max_num, upper)
            while i >= min_num:
                if i * i < p:  # Too small
                    break
                if p % i == 0:  # Found factor
                    j = p // i
                    if j <= max_num and j >= min_num:
                        # Step 4: Return modulo 1337
                        return p % 1337
                i -= 1
            left -= 1

        return 0  # Fallback (not reached due to problem guarantee)

• Line 3-4: Handle n=1 special case (9).
• Line 7-8: Set max (99) and min (10) for n-digit.
• Line 11-13: Construct palindrome (e.g., 9999).
• Line 16-24: Check factors:
• Upper bound = p // min_num.
• Test i from max to min, ensure i * j = p.
• Return p % 1337 if both factors n-digit.
• Time Complexity: O(10^n)—left half decrements, factor checks bounded.
• Space Complexity: O(1)—minimal space.

It’s like a palindrome-crafting spell!

Alternative Solution: Brute Force Enumeration

Why an Alternative Approach?

The brute force enumeration—O(10^(2n)) time, O(1) space—tests all pairs of n-digit numbers, computes their products, checks for palindromes, and tracks the largest, applying modulo 1337. It’s slow but intuitive, like mixing every potion pair to find the grandest mirror. Good for small n or learning!

How It Works

• Step 1: Iterate all pairs (i, j) from max to min.
• Step 2: Compute product, check if palindrome.
• Step 3: Track largest palindrome.
• Step 4: Return result % 1337.

Step-by-Step Example

Example: n = 2

• Pairs: 99*99 = 9801 (pal), 99*98 = 9702, …, 99*91 = 9009 (pal).
• Largest: 9801.
• Result: 9801 % 1337 = 987 (but 9009 is correct per problem).

Code for Brute Force

Copy codeclass Solution:
    def largestPalindrome(self, n: int) -> int:
        def is_palindrome(num):
            return str(num) == str(num)[::-1]

        max_num = 10 ** n - 1
        min_num = 10 ** (n - 1)
        largest = 0

        for i in range(max_num, min_num - 1, -1):
            for j in range(i, min_num - 1, -1):
                prod = i * j
                if prod <= largest:  # Early break
                    break
                if is_palindrome(prod):
                    largest = max(largest, prod)

        return largest % 1337

• Line 3-4: Check if number is palindrome.
• Line 10-16: Test pairs, update largest palindrome.
• Line 18: Return modulo 1337.
• Time Complexity: O(10^(2n))—n-digit pairs.
• Space Complexity: O(1)—minimal space.

It’s a slow potion mixer!

Comparing the Two Solutions

• Mathematical Construction (Best):
• Pros: O(10^n), fast, scalable.
• Cons: Requires math insight.
• Brute Force (Alternative):
• Pros: O(10^(2n)), simple.
• Cons: Impractical for n > 3.

Math wins for efficiency.

Edge Cases and Examples

• Input: n=1 → 9.
• Input: n=8 → 688 (precomputed).
• Input: n=2 → 911.

Math handles all well.

Complexity Recap

• Math: Time O(10^n), Space O(1).
• Brute Force: Time O(10^(2n)), Space O(1).

Math’s the champ.

Key Takeaways

• Math: Construct smartly.
• Brute Force: Test all pairs.
• Python Tip: Math trumps loops—see [Python Basics](/python/basics).

Final Thoughts: Craft That Palindrome

LeetCode 479: Largest Palindrome Product in Python is a palindrome-crafting magical quest. Mathematical construction is your fast spell, while brute force is a slow brew. Want more number fun? Try LeetCode 9: Palindrome Number or LeetCode 415: Add Strings. Ready to conjure some palindromes? Head to Solve LeetCode 479 on LeetCode and cast it today—your coding skills are magic-ready!