Find the Largest Palindromic Product of Equal-Length Factors
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
# Find the Largest Palindromic Product of Equal-Length Factors
Given `n`, find the largest integer that is both a decimal palindrome and the product of two positive integers having exactly `n` decimal digits each. The two factors may be equal.
Return that largest integer modulo `1337`. Maximize the unreduced product first; the goal is not to maximize its remainder.
### Interface
`class Solution { public: int largestPalindrome(int n); };`
### Example 1
```text
Input: n = 3
Output: 123
```
The largest qualifying product is `993 * 913 = 906609`. It reads the same in either direction, and `906609 = 1337 * 678 + 123`.
### Example 2
```text
Input: n = 4
Output: 597
```
The largest qualifying product is `9999 * 9901 = 99000099`. Its remainder is 597 because `99000099 = 1337 * 74046 + 597`.
### Constraints
- `1 <= n <= 8`.
- Both factors must be positive `n`-digit integers; leading zeros do not create extra digits.
### What a Strong Answer Covers
- Why the selected palindrome is the largest feasible product.
- Exact factor-length checks and applying the modulus only after selection.
- The one-digit case and arithmetic wide enough for eight-digit factors.
- An honest bound on the amount of searching and the memory used.
```hint Candidate order
Can palindromes be generated directly in decreasing order, rather than checking every possible product?
```
Overview: Find the largest decimal palindrome formed by two n-digit factors and return its remainder modulo 1337, preserving the full one-to-eight-digit domain.