Largest Palindrome Product

Largest Palindrome Product

1. What is this problem about?

The Largest Palindrome Product coding problem asks you to find the largest palindrome made from the product of two n-digit integers. Since the resulting number can be very large, you are often asked to return the result modulo 1337. For example, if n=2, the largest product of two 2-digit numbers (up to 99) that is a palindrome is 9009 (91 * 99).

2. Why is this asked in interviews?

Yahoo and other companies use this "Hard" level problem to test mathematical intuition and optimization skills. It requires more than just brute-force multiplication; you need to intelligently search for palindromes in descending order. It evaluates your ability to handle large numbers and implement efficient loops that can terminate early.

3. Algorithmic pattern used

This utilizes the Math and Enumeration interview pattern. Instead of iterating through all products, a better approach is to iterate through possible palindromes. You start by creating the largest possible n-digit palindrome (e.g., for n=2, start with 9999, then 9889, etc.) and then check if that palindrome has two n-digit factors. This "reverse construction" of palindromes is much more efficient than checking every product for the palindrome property.

4. Example explanation

For n=1:

• Max 1-digit numbers: 9.
• Possible products: 99=81, 98=72, ... 3*3=9.
• Largest palindrome is 9. For n=2:
• Max 2-digit number: 99.
• Start checking palindromes from 9999 downwards:
• 9999 (not divisible by two 2-digit numbers)
• ...
• 9009: 9009 / 99 = 91. Both 99 and 91 are 2-digit numbers.
• Answer: 9009.

5. Common mistakes candidates make

A common error is a pure brute-force approach (multiplying all n-digit numbers), which becomes incredibly slow as n increases. Another mistake is failing to handle the modulo 1337 requirement correctly or not optimizing the inner loop to stop when the divisor's square is less than the palindrome. Some candidates also struggle with the logic of constructing palindromes from a numeric half.

6. Interview preparation tip

For "Math, Enumeration interview pattern" problems, always think about the direction of your search. Searching from the largest possible result downwards (greedy approach) allows you to return the very first valid answer you find, which is often much faster than finding all answers and then taking the max.