01 Aug 2025•PHP•Hard

Largest Palindrome Product

find the largest palindrome made from the product of two n-digit numbers using brute force with optimizations.

View original LeetCode question

generate palindromes in descending order, then check if they can be factored into two n-digit numbers. start from the largest possible palindrome and work downwards.

for each palindrome, try to find factors by checking divisors from the largest n-digit number down. early termination when factors become too small.

optimization

generate palindromes efficiently by mirroring the first half. check divisibility starting from largest possible factor to minimize iterations.

complexity

O(10^(2n)) worst case, but optimizations make it much faster in practice. O(1) space.

Solution files

PHP•largest-palindrome-product/solution.php
class Solution {

function largestPalindrome($n) {
    if ($n == class="syntax-number">1) {
        return class="syntax-number">9;
    }
    
    $upper_limit = pow(class="syntax-number">10, $n) - class="syntax-number">1;
    $lower_limit = pow(class="syntax-number">10, $n - class="syntax-number">1);
    
    for ($i = $upper_limit; $i >= $lower_limit; $i--) {
        $palindrome = intval(strval($i) . strrev(strval($i)));
        $j = $upper_limit;
        while ($j * $j >= $palindrome) {
            if ($palindrome % $j == class="syntax-number">0 && $lower_limit <= $palindrome / $j && $palindrome / $j <= $upper_limit) {
                return $palindrome % class="syntax-number">1337;
            }
            $j--;
        }
    }
    
    return -class="syntax-number">1;
}
}