LeetCode Solutions Blog

Largest Palindrome Product

Number: 479

Difficulty: Hard

Paid? No

Companies: Yahoo

Problem Description

Given an integer n, find the largest palindromic integer that is the product of two n-digit numbers. Since the product can be very large, return the result modulo 1337.

Key Insights

Instead of checking every pair of n-digit numbers, generate candidate palindromes by constructing them from their first half.
Once a candidate palindrome is generated, verify if it can be factored into two n-digit numbers.
Use early termination within the factorization check by breaking when a factor multiplied by itself becomes less than the candidate.
This method significantly reduces the number of checks needed compared to brute force.

Space and Time Complexity

Time Complexity: O(10^(n)) in the worst-case scenario, given the iteration over possible halves. Space Complexity: O(1) since only a constant amount of extra space is used.

Solution

The solution generates palindromic numbers by mirroring a candidate half and then checks if the palindrome can be written as the product of two n-digit factors. The key data structures used are simple integer variables and loops. The algorithm takes advantage of the symmetric nature of palindromes to reduce the overall search space and uses early breaks in the factor checking loop when further checking becomes unnecessary.

Code Solutions

# Python solution with detailed comments
class Solution:
    def largestPalindrome(self, n: int) -> int:
        # For n = 1, the largest palindrome is 9 (i.e., 1-digit scenario)
        if n == 1:
            return 9
        
        # The highest and lowest n-digit numbers
        upper_bound = 10**n - 1
        lower_bound = 10**(n - 1)
        
        # Function to verify if a palindrome can be factorized into two n-digit numbers
        def has_factors(palindrome: int) -> bool:
            for factor in range(upper_bound, lower_bound - 1, -1):
                # Verify if 'factor' is a divisor and its corresponding quotient is an n-digit number
                if palindrome % factor == 0:
                    other = palindrome // factor
                    if lower_bound <= other <= upper_bound:
                        return True
                # If factor squared is less than palindrome, no further valid factors exist
                if factor * factor < palindrome:
                    break
            return False
        
        # Candidate maximum based on the product of two n-digit numbers
        max_num = upper_bound * upper_bound
        digits = len(str(max_num))
        half_length = (digits + 1) // 2  # Determine the length of the first half
        
        # Iterate over all possible first halves in descending order
        for first_half in range(10**half_length - 1, 10**(half_length - 1) - 1, -1):
            str_half = str(first_half)
            # Construct the palindrome by appending the reverse of the first half
            candidate = int(str_half + str_half[::-1])
            if has_factors(candidate):
                return candidate % 1337
        return -1