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 <= 8The key idea in #479 Largest Palindrome Product is to avoid checking every product of two n-digit numbers. A brute-force approach multiplies all pairs and checks if the result is a palindrome, but this becomes extremely expensive as the search space grows.
A more efficient strategy uses mathematical observation and enumeration. Instead of generating products first, we can construct palindromes directly by taking a number as the first half and mirroring it to form a full palindrome. For each generated palindrome, we then check whether it can be factored into two n-digit numbers. If such a factorization exists, we have found a valid palindrome product.
To speed up the check, iterate potential divisors from the largest n-digit number downward and stop once the divisor squared becomes smaller than the palindrome. This pruning significantly reduces unnecessary checks. Finally, the result is returned modulo 1337 as required.
This approach dramatically narrows the search space compared to naive enumeration while keeping space usage minimal.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force Pair Enumeration | O(10^(2n)) | O(1) |
| Palindrome Generation + Factor Check | Approximately O(10^(n/2) * 10^n) in worst case with heavy pruning | O(1) |
NeetCode
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
While the exact problem may not appear frequently, similar questions involving palindrome generation, mathematical optimization, and search-space reduction are common in technical interviews at top companies.
The optimal approach constructs palindromes directly instead of checking every product of two numbers. By generating palindromes from the highest possible half and checking whether they can be factored into two n-digit numbers, the search space is greatly reduced.
Checking every product of two n-digit numbers creates a huge number of combinations. Generating palindromes first dramatically reduces candidates, allowing us to test only numbers that could actually satisfy the palindrome condition.
This problem mainly relies on mathematical reasoning and enumeration rather than complex data structures. Simple integer variables and loops are sufficient, since the key optimization comes from generating palindromes and verifying valid factors.