HardNo. 0479

Largest Palindrome Product — LeetCode 479 Python Solution

Topics
Math, Enumeration
Reading time
3 min

The 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.

Example

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

Python solution

PythonSolution
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

Complexity

Time
O(n) or O(1)
Space · auxiliary
O(1)

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 479. Largest Palindrome Product is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Math.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0204Count PrimesMedium
0829Consecutive Numbers SumHard
0906Super PalindromesHard
1925Count Square Sum TriplesEasy
1952Three DivisorsEasy
2081Sum of k-Mirror NumbersHard

Frequently asked questions

How hard is LeetCode 479. Largest Palindrome Product?

LeetCode 479. Largest Palindrome Product is rated Hard on LeetCode.

What topics does LeetCode 479. Largest Palindrome Product cover?

LeetCode 479. Largest Palindrome Product is tagged Math and Enumeration on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.