Watch 7 video solutions for Largest Palindrome Product, a hard level problem involving Math, Enumeration. This walkthrough by 傅码爷 has 1,184 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |