# Largest Palindrome Product
**Difficulty:** HARD
[External](https://leetcode.com/problems/largest-palindrome-product)
Canonical: https://scaleengineer.com/dsa/problems/largest-palindrome-product
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
---
## Problem
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 <= 8`

# Approaches
## Brute-Force Product Checking
This approach involves a straightforward brute-force search. It iterates through all possible pairs of n-digit numbers, starting from the largest ones. For each pair, it computes their product and checks if the product is a palindrome. It keeps track of the largest palindromic product found.
**Time:** O(10^(2n)). The number of n-digit numbers is approximately `9 * 10^(n-1)`. The nested loops result in a complexity that is roughly the square of this number. This is computationally expensive and not feasible for the given constraints. · **Space:** O(n), where n is the number of digits. This space is used to store the string representation of the product, which can have up to 2n digits.
**Pros:** Simple to understand and implement.; Guaranteed to find the correct answer.
**Cons:** Extremely inefficient for larger values of `n`.; Will result in a 'Time Limit Exceeded' error on most platforms for `n > 4`.
### Explanation
The algorithm defines the range for n-digit numbers, which is from `10^(n-1)` to `10^n - 1`. It then uses two nested loops to explore all unique pairs of numbers within this range. To find the largest palindrome faster, the loops iterate downwards from the highest n-digit number.

For each product, a helper function `isPalindrome` is used to verify if it's a palindrome. If a palindromic product is found that is larger than the current maximum, the maximum is updated. A small optimization is included: since the inner loop also iterates downwards, if the current product becomes less than the largest palindrome found so far, we can break out of the inner loop, as no larger product can be found for the current outer loop iteration.

```java
class Solution {
    public int largestPalindrome(int n) {
        if (n == 1) {
            return 9;
        }
        long upper = (long) Math.pow(10, n) - 1;
        long lower = (long) Math.pow(10, n - 1);
        long maxPalindrome = 0L;

        for (long i = upper; i >= lower; i--) {
            for (long j = i; j >= lower; j--) {
                long product = i * j;
                if (product < maxPalindrome) {
                    // Since j is decreasing, further products for this i will also be smaller.
                    break;
                }
                if (isPalindrome(product)) {
                    maxPalindrome = product;
                }
            }
        }
        return (int) (maxPalindrome % 1337);
    }

    private boolean isPalindrome(long num) {
        String s = Long.toString(num);
        int len = s.length();
        for (int i = 0; i < len / 2; i++) {
            if (s.charAt(i) != s.charAt(len - 1 - i)) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Handle the base case where `n = 1`, returning 9.
- Determine the range of n-digit numbers. The upper bound is `upper = 10^n - 1` and the lower bound is `10^(n-1)`.
- Initialize a variable `maxPalindrome` to 0 to store the largest palindrome found.
- Use a nested loop to iterate through all pairs of n-digit numbers. The outer loop for `i` runs from `upper` down to `lower`.
- The inner loop for `j` runs from `i` down to `lower` to avoid duplicate products (`i*j` and `j*i`).
- Inside the inner loop, calculate the product `p = i * j`.
- As an optimization, if `p` is already smaller than `maxPalindrome`, we can break the inner loop because subsequent products for the current `i` will be even smaller.
- Check if `p` is a palindrome. This can be done by converting the number to a string and checking if it reads the same forwards and backward.
- If `p` is a palindrome, update `maxPalindrome = p`.
- After the loops complete, return `maxPalindrome % 1337`.

## Construct Palindromes and Check Factors
Instead of checking every possible product, this more efficient approach generates palindromic numbers and then checks if they have two n-digit factors. By generating palindromes from largest to smallest, the first one that satisfies the condition is guaranteed to be the answer. This dramatically reduces the search space.
**Time:** O(10^n). The outer loop iterates through `O(10^n)` potential palindrome halves. The inner loop runs for a small number of iterations for the palindromes near the top of the range, as the factors will be close to the palindrome's square root. Therefore, the complexity is dominated by the outer loop. · **Space:** O(n), where n is the number of digits. This space is needed to create the string representation of the palindrome's left half.
**Pros:** Significantly more efficient than brute-force.; Capable of solving the problem within the time limits for `n` up to 8.
**Cons:** The logic is more complex than the brute-force approach.; It relies on the assumption that the largest palindrome has 2n digits, which holds for n > 1 but requires some mathematical insight.
### Explanation
This method is based on the observation that for `n > 1`, the largest palindrome formed by the product of two n-digit numbers will have `2n` digits. A `2n`-digit palindrome is symmetric, so it can be constructed from its first `n` digits (the 'left half').

The algorithm iterates through all possible `n`-digit left halves, starting from the largest (`10^n - 1`) and going downwards. For each left half, it constructs the full palindrome. For example, if `n=3` and the left half is `998`, the full palindrome is `998899`.

Once a palindrome `p` is constructed, the algorithm checks if it's a product of two n-digit numbers. It does this by iterating a potential factor `i` from the largest n-digit number downwards. An important optimization is to stop the search for `i` when `i * i < p`. This is because if `i` were smaller than the square root of `p`, the other factor `p/i` would be larger than `i`, and we would have found the factorization when testing that larger factor.

Because we start with the largest possible palindromes, the first one we can factor into two n-digit numbers is our answer.

```java
class Solution {
    public int largestPalindrome(int n) {
        if (n == 1) {
            return 9;
        }
        long upper = (long) Math.pow(10, n) - 1;

        // Iterate through the first half of the palindrome (left part)
        for (long left = upper; left > upper / 10; left--) {
            // Construct the full palindrome from the left part
            long p = createPalindrome(left);

            // Find a factor for this palindrome
            // The factor 'i' must be at most 'upper'.
            // We check i*i >= p because if i < sqrt(p), then the other factor p/i > sqrt(p),
            // and we would have found this pair when checking the larger factor.
            for (long i = upper; i * i >= p; i--) {
                if (p % i == 0) {
                    // Found a factor. Since we iterate from the largest palindrome,
                    // this is the largest palindrome product.
                    return (int) (p % 1337);
                }
            }
        }
        return -1; // Should not be reached for n > 1
    }

    private long createPalindrome(long num) {
        String s = Long.toString(num);
        String reversedS = new StringBuilder(s).reverse().toString();
        return Long.parseLong(s + reversedS);
    }
}
```
### Algorithm
- Handle the base case where `n = 1`, returning 9.
- The largest palindrome product of two n-digit numbers will have `2n` digits (for `n > 1`). Such a palindrome is determined by its first `n` digits (the 'left half').
- Calculate the upper bound for an n-digit number: `upper = 10^n - 1`.
- Iterate through possible left halves, from `upper` downwards.
- For each `left` half, construct the full palindrome `p`. For a `left` value `xyz`, the palindrome is `xyzyx`.
- Now, check if `p` can be factored into two n-digit numbers. Iterate a potential factor `i` from `upper` downwards.
- The search for `i` can be optimized. We only need to check `i` down to `sqrt(p)`. If `i < sqrt(p)`, the other factor `p/i` would be larger than `i`, and we would have already encountered it as a potential factor. So, the inner loop condition is `i * i >= p`.
- If `p` is divisible by `i` (i.e., `p % i == 0`), we have found a valid pair of n-digit factors (`i` and `p/i`).
- Since we are generating palindromes from the largest possible downwards, the first one for which we find a valid factorization is the largest possible palindrome product.
- Return the result `p % 1337`.

# Solutions
### Java

```java
class Solution {
public
  int largestPalindrome(int n) {
    int mx = (int)Math.pow(10, n) - 1;
    for (int a = mx; a > mx / 10; --a) {
      int b = a;
      long x = a;
      while (b != 0) {
        x = x * 10 + b % 10;
        b /= 10;
      }
      for (long t = mx; t * t >= x; --t) {
        if (x % t == 0) {
          return (int)(x % 1337);
        }
      }
    }
    return 9;
  }
}

```

### Python

```python
class Solution:
    def largestPalindrome(self, n: int) -> int: mx = 10 ** n - 1 for a in range(mx, mx // 10, - 1): b = x = a while b: x = x * 10 + b % 10 b //= 10 t = mx while t * t >= x: if x % t == 0: return x % 1337 t -= 1 return 9

```

### CPP

```cpp
class Solution {
public:
  int largestPalindrome(int n) {
    int mx = pow(10, n) - 1;
    for (int a = mx; a > mx / 10; --a) {
      int b = a;
      long x = a;
      while (b) {
        x = x * 10 + b % 10;
        b /= 10;
      }
      for (long t = mx; t * t >= x; --t)
        if (x % t == 0)
          return x % 1337;
    }
    return 9;
  }
};

```