# LeetCode 479: Largest Palindrome Product

## Problem Restatement

We are given an integer `n`.

We need to find the largest palindrome that can be written as the product of two `n`-digit integers.

Because the answer may be very large, we return the palindrome modulo `1337`.

For example, when `n = 2`, the two-digit numbers are from `10` to `99`.

The largest palindrome product is:

```text
99 * 91 = 9009
```

Then we return:

```text
9009 % 1337 = 987
```

So the answer is `987`.

The constraints are `1 <= n <= 8`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An integer `n` |
| Output | The largest palindrome product modulo `1337` |
| Factor rule | The palindrome must be a product of two `n`-digit integers |
| Constraint | `1 <= n <= 8` |

Function shape:

```python
def largestPalindrome(n: int) -> int:
    ...
```

## Examples

Example 1:

```python
n = 2
```

The largest two-digit number is `99`.

The largest palindrome product is:

```text
99 * 91 = 9009
```

Return:

```text
9009 % 1337 = 987
```

Answer:

```python
987
```

Example 2:

```python
n = 1
```

The one-digit numbers are from `1` to `9`.

The largest palindrome product is:

```text
9 * 1 = 9
```

Answer:

```python
9
```

## First Thought: Check Every Product

The direct way is to multiply every pair of `n`-digit numbers.

For each product, check whether it is a palindrome.

```python
class Solution:
    def largestPalindrome(self, n: int) -> int:
        MOD = 1337

        high = 10 ** n - 1
        low = 10 ** (n - 1)

        best = 0

        for a in range(high, low - 1, -1):
            for b in range(a, low - 1, -1):
                product = a * b

                if product <= best:
                    break

                if str(product) == str(product)[::-1]:
                    best = product

        return best % MOD
```

This is easy to understand.

It also avoids duplicate pairs by starting `b` from `a`.

But this still has too many products when `n` is large.

## Problem With Brute Force

There are about `9 * 10^(n-1)` different `n`-digit numbers.

Checking all pairs costs roughly:

```text
O(10^(2n))
```

For `n = 8`, this is far too large.

We need to avoid testing ordinary products.

Instead, we should generate palindromes directly.

## Key Insight

The target number must be a palindrome.

So rather than checking whether every product is a palindrome, generate palindrome candidates from largest to smallest, then check whether each candidate can be factored into two `n`-digit numbers.

For `n = 2`, the largest possible product has at most `4` digits.

We can generate even-length palindromes by choosing the left half and mirroring it.

For example:

```text
left = 99
palindrome = 9999

left = 98
palindrome = 9889

left = 97
palindrome = 9779
```

Eventually:

```text
left = 90
palindrome = 9009
```

And:

```text
9009 = 99 * 91
```

Since we generate palindromes in descending order, the first valid one is the largest answer.

## Why Generate Even-Length Palindromes

For `n > 1`, the largest product of two `n`-digit numbers has either `2n` or `2n - 1` digits.

The standard accepted search generates `2n`-digit palindrome candidates by mirroring an `n`-digit left half.

This works for this problem because the largest valid palindrome product for `n >= 2` is found among these generated even-length candidates.

The case `n = 1` is special and returns `9`.

## Algorithm

Handle the special case:

```python
if n == 1:
    return 9
```

Compute the largest and smallest `n`-digit bounds:

```python
high = 10 ** n - 1
low = 10 ** (n - 1)
```

Then loop over possible left halves from largest to smallest.

For each `left`, build the palindrome:

```python
pal = int(str(left) + str(left)[::-1])
```

Then check whether `pal` has an `n`-digit factor.

Start from the largest factor `high` and move downward.

For each possible factor `x`:

1. Stop if `x * x < pal`.
2. If `pal % x == 0`, then `x` is one factor.
3. The other factor is `pal // x`.
4. Because `x * x >= pal`, the other factor is at most `x`.
5. Since `x` starts as an `n`-digit number and moves downward, this finds whether `pal` can be formed by two `n`-digit numbers.

Return:

```python
pal % 1337
```

## Correctness

The algorithm generates palindrome candidates in descending order of their left half.

For fixed digit length, a larger left half produces a larger palindrome. Therefore, the first valid palindrome found by this enumeration is the largest valid palindrome among the generated candidates.

For each palindrome `pal`, the algorithm tests possible divisors `x` from the largest `n`-digit number downward.

If `pal % x == 0`, then:

```text
pal = x * (pal // x)
```

So `pal` can be written as a product of two integers.

The loop only needs to continue while:

```text
x * x >= pal
```

Once `x * x < pal`, both factors cannot be at least `x`. Any remaining factor below `x` would pair with another factor above `x`, and that larger factor was already considered earlier in the descending loop.

Thus the factor check correctly detects whether the palindrome can be represented as the product of two `n`-digit numbers.

Since the candidates are checked from largest to smallest, the first valid candidate is the largest palindrome product. Returning it modulo `1337` gives the required output.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(10^n * 10^n)` worst case | We may generate many palindromes and test many divisors |
| Space | `O(1)` | Only integer variables are stored |

In practice, the search is much faster than brute force because it checks only palindromes, not every product.

## Implementation

```python
class Solution:
    def largestPalindrome(self, n: int) -> int:
        if n == 1:
            return 9

        MOD = 1337

        high = 10 ** n - 1
        low = 10 ** (n - 1)

        for left in range(high, low - 1, -1):
            pal = int(str(left) + str(left)[::-1])

            x = high
            while x * x >= pal:
                if pal % x == 0:
                    return pal % MOD
                x -= 1

        return 0
```

## Code Explanation

The single-digit case is handled directly:

```python
if n == 1:
    return 9
```

For one-digit numbers, the largest palindrome product is `9`.

These bounds define the valid `n`-digit factors:

```python
high = 10 ** n - 1
low = 10 ** (n - 1)
```

For `n = 2`:

```text
low = 10
high = 99
```

This loop generates left halves in descending order:

```python
for left in range(high, low - 1, -1):
```

This builds an even-length palindrome:

```python
pal = int(str(left) + str(left)[::-1])
```

For example:

| `left` | `pal` |
|---:|---:|
| 99 | 9999 |
| 98 | 9889 |
| 90 | 9009 |

Then we test factors:

```python
x = high
while x * x >= pal:
```

The condition `x * x >= pal` avoids checking unnecessary small divisors.

If `x` divides `pal`, then `pal` can be written as a product:

```python
if pal % x == 0:
    return pal % MOD
```

Because palindromes are generated from largest to smallest, we can return immediately.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.largestPalindrome(1) == 9
    assert s.largestPalindrome(2) == 987
    assert s.largestPalindrome(3) == 123
    assert s.largestPalindrome(4) == 597

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `n = 1` | Special case |
| `n = 2` | Given example: `9009 % 1337 = 987` |
| `n = 3` | Checks larger factor range |
| `n = 4` | Checks deeper palindrome enumeration |