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 1:
Input: n = 2 Output: 987 Explanation: 99 x 91 = 9009, 9009 % 1337 = 987
Example 2:
Input: n = 1 Output: 9
Constraints:
1 <= n <= 8Problem Overview: Given an integer n, find the largest palindrome made from the product of two n-digit numbers. The result must be returned modulo 1337. A brute force search works for small ranges, but smarter enumeration of palindromes reduces the search space significantly.
Approach 1: Brute Force with Optimization (Time: O(10^(2n)), Space: O(1))
Start from the largest n-digit number (10^n - 1) and iterate downward for both multiplicands. For each pair (i, j), compute the product and check whether the number is a palindrome by reversing its digits or converting it to a string. To reduce work, break the inner loop once the product drops below the best palindrome already found. Another small optimization is iterating j from i downward to avoid duplicate pairs. This approach relies on straightforward enumeration and palindrome checking, which fits naturally under enumeration and math techniques.
Approach 2: Constructing Palindromes First (Time: ~O(10^n), Space: O(1))
Instead of testing every product, generate palindrome candidates directly. Take a number representing the first half of the palindrome, mirror it to form a full palindrome, then check whether it can be factored into two n-digit numbers. For each generated palindrome p, iterate possible divisors from the largest n-digit value downward and check p % d == 0. If the complementary factor p / d also has n digits, the palindrome is valid. Because palindromes are generated in descending order, the first valid one is the largest. This approach drastically reduces the number of candidates compared with brute force and is the standard optimization using enumeration combined with numeric symmetry.
Recommended for interviews: Interviewers expect the palindrome-construction approach. Starting with brute force shows you understand the search space and basic palindrome checking. Switching to generating palindromes first demonstrates deeper reasoning about number symmetry and reduces the search from checking millions of products to testing a small set of structured candidates.
This method involves calculating the product of all pairs of two n-digit numbers and checking which of these products is a palindrome. We start from the largest possible two n-digit numbers and work our way down, allowing us to find the maximum palindrome early in the looping process. Stop iterating early if the palindrome has been discovered.
The solution iterates through potential n-digit number pairs in a descending order of magnitude, calculating their product and checking if it's a palindrome. By doing this in a descending order, the first palindrome found is the largest possible, thus shortening the loop cycles once it's discovered. The result is then taken modulo 1337 as required by the problem statement.
Time Complexity: O((10^n)^2) in the worst case, due to the nested iterations over n-digit numbers.
Space Complexity: O(1), as no additional space is used beyond integer storage.
Rather than exploring the entire solution space of n-digit number pairs, this approach first constructs palindromic numbers, then checks their composability as products of two n-digit numbers. By constructing palindromes directly, we constrain the problem, focusing directly on known feasible solutions.
This Python code constructs palindromes from large numbers down by appending reverse digits to form potential products. It then checks for composability as a product of two n-digit numbers, breaking early to optimize time when a solution is found.
Python
Time Complexity: O(10^n), where number of palindrome candidates is reduced compared to complete n-digit multiplicands.
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Brute Force with Optimization | Time Complexity: O((10^n)^2) in the worst case, due to the nested iterations over n-digit numbers. |
| Constructing Palindromes First | Time Complexity: O(10^n), where number of palindrome candidates is reduced compared to complete n-digit multiplicands. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Optimization | O(10^(2n)) | O(1) | Useful for understanding the search space or when n is very small |
| Constructing Palindromes First | ~O(10^n) | O(1) | Best practical solution; drastically reduces candidates by generating palindromes directly |
【每日一题：小Fu讲解】LeetCode 479. Largest Palindrome Product • 傅码爷 • 1,184 views views
Watch 6 more video solutions →Practice Largest Palindrome Product with our built-in code editor and test cases.
Practice on FleetCode