Code Implementation

class Solution:
    def largestPalindrome(self, n: int) -> int:
        if n == 1:
            return 9
        upper = 10 ** n - 1
        lower = 10 ** (n - 1)
        for first_half in range(upper, lower - 1, -1):
            p = int(str(first_half) + str(first_half)[::-1])
            for x in range(upper, lower - 1, -1):
                if p // x > upper:
                    break
                if p % x == 0:
                    return p % 1337
        return -1
      

class Solution {
public:
    int largestPalindrome(int n) {
        if (n == 1) return 9;
        long upper = pow(10, n) - 1;
        long lower = pow(10, n - 1);
        for (long first_half = upper; first_half >= lower; --first_half) {
            string s = to_string(first_half);
            string rev_s = s;
            reverse(rev_s.begin(), rev_s.end());
            long p = stol(s + rev_s);
            for (long x = upper; x >= lower; --x) {
                if (p / x > upper) break;
                if (p % x == 0) return p % 1337;
            }
        }
        return -1;
    }
};
      

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);
        for (long first_half = upper; first_half >= lower; --first_half) {
            String s = Long.toString(first_half);
            String pStr = s + new StringBuilder(s).reverse().toString();
            long p = Long.parseLong(pStr);
            for (long x = upper; x >= lower; --x) {
                if (p / x > upper) break;
                if (p % x == 0) return (int)(p % 1337);
            }
        }
        return -1;
    }
}
      

var largestPalindrome = function(n) {
    if (n === 1) return 9;
    let upper = Math.pow(10, n) - 1;
    let lower = Math.pow(10, n - 1);
    for (let first_half = upper; first_half >= lower; --first_half) {
        let s = first_half.toString();
        let rev_s = s.split('').reverse().join('');
        let p = parseInt(s + rev_s, 10);
        for (let x = upper; x >= lower; --x) {
            if (Math.floor(p / x) > upper) break;
            if (p % x === 0) return p % 1337;
        }
    }
    return -1;
};
      

Problem Description

Given an integer n, find the largest palindrome made from the product of two n-digit numbers, and return it modulo 1337. For example, if n = 2, you are to find the largest palindrome made from the product of two 2-digit numbers (i.e., numbers between 10 and 99). The result should be the palindrome modulo 1337.

Constraints:

• 1 <= n <= 8
• The answer is guaranteed to exist for the given input range.

Thought Process

At first glance, the problem looks like a brute-force search: multiply all pairs of n-digit numbers and check if the product is a palindrome, keeping track of the largest. However, this approach is computationally expensive, especially for large n. The number of pairs grows rapidly as n increases.

To optimize, we can flip the process: instead of generating all products and checking for palindromes, we can generate palindromes in decreasing order and check if they can be factored into two n-digit numbers. Since we want the largest palindrome, we start from the top and stop at the first valid one.

This approach is much more efficient because there are far fewer palindromes than products. We only need to check if a palindrome can be written as a product of two n-digit numbers.

Solution Approach

Here’s how we can solve the problem step-by-step:

1. Special Case for n = 1:
   • For single-digit numbers, the largest palindrome is 9 (9 x 1 = 9).
2. Set the Range:
   • The largest n-digit number is upper = 10^n - 1.
   • The smallest n-digit number is lower = 10^{n-1}.
3. Generate Palindromes:
   • Since the largest palindrome is likely to have even digits, construct palindromes by taking a number first_half and appending its reverse to itself.
   • For example, if first_half = 99, palindrome = 9999.
4. Check for Valid Factors:
   • For each palindrome, check if it can be factored into two n-digit numbers.
   • Loop over possible divisors x from upper down to lower.
   • If palindrome / x is within the n-digit range and divides evenly, we've found our answer.
5. Return the Result Modulo 1337:
   • Return the palindrome modulo 1337 as required.

This method is efficient because it checks only as many palindromes as necessary, and stops as soon as the largest valid one is found.

Example Walkthrough

Let’s walk through the process for n = 2:

• upper = 99, lower = 10
• Start with first_half = 99 and build palindrome: "99" + "99" reversed = "9999".
• Check if 9999 can be written as a product of two 2-digit numbers:
  • 9999 / 99 = 101.00 (not a 2-digit number)
  • 9999 / 98 = 101.01 (not integer)
  • And so on...
• Continue with first_half = 98: palindrome = 9889.
• Repeat the process until 9009 is reached.
• 9009 / 91 = 99, and both 91 and 99 are 2-digit numbers. So, 9009 is the largest palindrome product for n = 2.
• Return 9009 % 1337 = 987.

Time and Space Complexity

• Brute-Force Approach:
  • Time Complexity: O(N²), where N = 10ⁿ (number of n-digit numbers). For each pair, check if the product is a palindrome.
  • Space Complexity: O(1), since only a few variables are used.
• Optimized Approach (Generating Palindromes):
  • Time Complexity: O(N), since we generate about N palindromes, and for each, check up to N possible divisors (but we break early when not possible).
  • Space Complexity: O(1), as only a constant amount of extra space is used.
• Why the Optimized Approach is Better:
  • We avoid checking all possible products, and instead focus only on palindromic candidates, drastically reducing the number of checks.

Summary

The key insight for solving the Largest Palindrome Product problem efficiently is to generate palindromes directly and check if they can be factored into two n-digit numbers, rather than brute-forcing all products. This approach leverages the properties of palindromes and reduces the computational workload dramatically. By starting from the largest possible palindrome and working downward, we ensure we find the correct answer quickly and efficiently.