Largest Palindrome Product Python Solution

Tested Python solution for LeetCode 479 with 12 pytest cases. Generate a practice environment with lcpy.

LeetCode 479, Hard. Topics: Math, Enumeration. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 12 parametrized pytest cases, and a playground notebook:

lcpy gen -n 479   # by problem number
lcpy gen -s largest_palindrome_product   # by problem name

​

Problem

Given an integer n, return the largest palindromic integer that can be represented as the product of two n-digits integers. Since the answer can be very large, return it modulo 1337.

​

Examples

Input: n = 2
Output: 987
Explanation: 99 x 91 = 9009, 9009 % 1337 = 987

Input: n = 1
Output: 9

​

Constraints

• 1 <= n <= 8

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(10^n) over the first half, each candidate factorized in O(10^(n/2))
    # Space: O(1)
    def largest_palindrome(self, n: int) -> int:
        if n == 1:
            return 9
        upper = 10**n - 1
        lower = 10 ** (n - 1)
        for half in range(upper, lower - 1, -1):
            s = str(half)
            cand = int(s + s[::-1])
            factor = upper
            while factor * factor >= cand:
                if cand % factor == 0:
                    return cand % 1337
                factor -= 1
        raise AssertionError("no palindrome found")

​

Complexity

Time	Space
O(10^n) over the first half, each candidate factorized in O(10^(n/2))	O(1)

​

Tags