LeetCode Problem 479

Difficulty: 🔴 Hard
Topics: Math, Enumeration

Solution

Largest Palindrome Product

Problem Understanding

The problem asks us to find the largest palindrome number that can be written as the product of two n-digit integers.

A palindrome is a number that reads the same forward and backward. For example, 9009 is a palindrome because reversing its digits still gives 9009.

The input is a single integer n, where n represents the number of digits in each multiplicand. For example:

• If n = 2, the valid numbers range from 10 to 99
• If n = 3, the valid numbers range from 100 to 999

We must search for the largest palindrome that can be expressed as:

$$a \times b$$

where both a and b are n-digit integers.

The problem does not ask us to return the palindrome itself. Instead, we return:

$$\text{palindrome} \bmod 1337$$

This modulus requirement exists because the palindrome can become extremely large for larger values of n.

The constraint is:

• 1 <= n <= 8

This upper bound is very important. A naive brute force solution would require checking products of numbers as large as 99,999,999, which is computationally infeasible.

An important observation is that the search space grows quadratically:

$$(10^n)^2$$

For n = 8, this becomes enormous, so we need a smarter strategy.

There are several important edge cases:

• n = 1 is special because the largest palindrome is simply 9
• Very large palindromes may exceed 32-bit integer limits, so languages like Go must use 64-bit integers
• A naive palindrome check repeated millions of times becomes prohibitively expensive
• The largest palindrome is not necessarily the square of the largest n-digit number

The problem guarantees that n is always valid and within the allowed range.

Approaches

Brute Force Approach

The most direct solution is to generate every possible product of two n-digit numbers and check whether the product is a palindrome.

For example, when n = 2, we would iterate:

• 99 * 99
• 99 * 98
• 99 * 97
• and so on

For each product:

1. Convert the number to a string
2. Reverse the string
3. Compare with the original
4. Track the maximum palindrome found

This approach is correct because it examines every possible pair of n-digit numbers. Eventually, it will encounter the largest valid palindrome.

However, the time complexity is far too large.

For n = 8, there are approximately:

$$(9 \times 10^7)^2$$

pairs to examine, which is completely impractical.

The brute force method also wastes substantial work checking non-palindromic numbers.

Optimal Approach

The key insight is that instead of generating products and checking whether they are palindromes, we can generate palindromes directly.

This drastically reduces the search space.

Suppose we construct palindromes by taking a number and appending its reverse:

• 91 -> 9119
• 900 -> 900009

If we generate palindromes from largest to smallest, then the first palindrome that can be factored into two n-digit numbers must be the answer.

The second major insight is factor checking.

If a palindrome p can be written as:

$$p = a \times b$$

then one factor must be at least:

$$\sqrt{p}$$

So we only need to search divisors downward from the largest n-digit number.

This turns an impossible brute force search into a manageable enumeration problem.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(10^(2n) * n)	O(1)	Checks every product and tests palindromes
Optimal	Roughly O(10^n * 10^(n/2)) in practice	O(1)	Generates palindromes directly and searches factors efficiently

Algorithm Walkthrough

Step 1: Handle the Special Case

If n == 1, return 9.

The largest product of two 1-digit numbers is:

$$9 \times 9 = 81$$

The largest palindromic product is:

$$9 = 9 \times 1$$

and:

$$9 \bmod 1337 = 9$$

Step 2: Determine the Largest and Smallest n-Digit Numbers

Compute:

• upper = 10^n - 1
• lower = 10^(n - 1)

For n = 2:

• upper = 99
• lower = 10

These bounds define the valid factor range.

Step 3: Generate Palindromes from Largest to Smallest

Start from left = upper.

Construct a palindrome by:

1. Converting left to a string
2. Reversing it
3. Appending the reverse

For example:

• left = 99
• reverse = 99
• palindrome = 9999

Then:

• left = 98
• palindrome = 9889

This guarantees descending palindrome order.

Step 4: Search for Valid Factors

For each palindrome:

1. Start divisor d = upper
2. While d * d >= palindrome
3. Check whether palindrome % d == 0

If divisible:

$$other = palindrome / d$$

Then verify:

• other >= lower
• other <= upper

If true, both factors are valid n-digit numbers.

Step 5: Return the Modulo

Once the first valid palindrome is found:

$$return palindrome \bmod 1337$$

Because palindromes are generated in descending order, the first valid one is guaranteed to be the largest.

Why it works

The algorithm generates palindromes from largest to smallest. For each palindrome, it checks whether the palindrome has two valid n-digit factors.

Since every larger palindrome is checked before smaller ones, the first palindrome that satisfies the factorization condition must be the maximum valid answer.

The divisor search is correct because any factor pair must contain a factor at least as large as the square root of the palindrome. Therefore, checking divisors down to that boundary guarantees we do not miss any valid factorization.

Python Solution

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

        upper = 10 ** n - 1
        lower = 10 ** (n - 1)

        for left in range(upper, lower - 1, -1):
            palindrome = int(str(left) + str(left)[::-1])

            divisor = upper

            while divisor * divisor >= palindrome:
                if palindrome % divisor == 0:
                    other = palindrome // divisor

                    if lower <= other <= upper:
                        return palindrome % 1337

                divisor -= 1

        return -1

The implementation begins with the special case for n == 1, because this case has a known direct answer.

Next, the code computes the upper and lower bounds for valid n-digit numbers.

The outer loop generates palindromes in descending order. Instead of testing every product, the code constructs candidate palindromes directly by mirroring the left half.

For each palindrome, the inner loop searches for a valid divisor. The condition:

divisor * divisor >= palindrome

ensures we only search until the square root boundary.

When divisibility is found, the paired factor is computed with integer division. If both factors are within the valid range, the palindrome satisfies the problem requirements, and we immediately return the modulo result.

The algorithm terminates early because the palindromes are generated from largest to smallest.

Go Solution

package main

import (
	"strconv"
)

func largestPalindrome(n int) int {
	if n == 1 {
		return 9
	}

	upper := intPow(10, n) - 1
	lower := intPow(10, n-1)

	for left := upper; left >= lower; left-- {
		palindrome := buildPalindrome(left)

		for divisor := upper; divisor*divisor >= palindrome; divisor-- {
			if palindrome%divisor == 0 {
				other := palindrome / divisor

				if other >= lower && other <= upper {
					return palindrome % 1337
				}
			}
		}
	}

	return -1
}

func buildPalindrome(x int) int {
	s := strconv.Itoa(x)
	reversed := reverseString(s)

	value, _ := strconv.Atoi(s + reversed)
	return value
}

func reverseString(s string) string {
	runes := []rune(s)

	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}

	return string(runes)
}

func intPow(base int, exp int) int {
	result := 1

	for exp > 0 {
		result *= base
		exp--
	}

	return result
}

The Go implementation follows the same logic as the Python version.

One important difference is integer handling. Go uses fixed-width integers, so using int is safe here because the maximum palindrome for n <= 8 still fits within 64-bit integer ranges on modern systems.

Unlike Python, Go does not have built-in string reversal utilities, so a helper function is used to reverse the string representation when constructing palindromes.

Go also does not provide a built-in integer exponentiation operator, so a small helper function computes powers of ten.

Worked Examples

Example 1

Input:

n = 2

We compute:

Variable	Value
upper	99
lower	10

Generate palindromes:

left	palindrome
99	9999
98	9889
97	9779
...	...
90	9009

Now check 9009.

divisor	9009 % divisor	valid?
99	0	yes

Compute:

$$9009 / 99 = 91$$

Both 99 and 91 are 2-digit numbers.

Therefore:

$$9009 \bmod 1337 = 987$$

Return:

987

Example 2

Input:

n = 1

Special case immediately returns:

9

because the largest palindromic product is 9.

Complexity Analysis

Measure	Complexity	Explanation
Time	Roughly O(10^n * 10^(n/2)) in practice	Generates palindromes and checks divisors efficiently
Space	O(1)	Only a few integer variables are used

The exact runtime is difficult to express tightly because the algorithm terminates early once the largest valid palindrome is found.

The important improvement over brute force is that we avoid enumerating all products. Instead, we enumerate palindrome candidates directly, which dramatically reduces unnecessary work.

The algorithm uses constant extra memory because it stores only a few variables regardless of input size.

Test Cases

solution = Solution()

assert solution.largestPalindrome(1) == 9       # smallest valid n
assert solution.largestPalindrome(2) == 987     # provided example
assert solution.largestPalindrome(3) == 123     # known LeetCode result
assert solution.largestPalindrome(4) == 597     # larger palindrome search
assert solution.largestPalindrome(5) == 677     # stress medium-sized input
assert solution.largestPalindrome(6) == 1218    # larger search space
assert solution.largestPalindrome(7) == 877     # near upper constraints
assert solution.largestPalindrome(8) == 475     # maximum allowed n

Test Summary

Test	Why
n = 1	Validates special-case handling
n = 2	Confirms provided example
n = 3	Tests standard larger search
n = 4	Verifies correctness on bigger palindromes
n = 5	Exercises more extensive divisor checking
n = 6	Tests performance on larger inputs
n = 7	Ensures scaling remains correct
n = 8	Validates maximum constraint

Edge Cases

Edge Case 1: n = 1

This is the most important special case. The palindrome generation strategy used for larger values creates even-length palindromes only, such as 9009 or 9889.

For n = 1, the correct answer is the single-digit palindrome 9.

Without explicitly handling this case, the algorithm would fail to return the correct result.

The implementation solves this immediately with:

if n == 1:
    return 9

Edge Case 2: Very Large Products

For n = 8, the palindrome can become very large. A naive implementation using 32-bit integers may overflow.

The Python version handles this naturally because Python integers have arbitrary precision.

The Go solution relies on modern 64-bit integer support, which safely accommodates the required values.

Edge Case 3: No Early Divisor Pruning

A naive divisor search might check all possible divisors down to 1.

This is unnecessary because once:

$$d^2 < palindrome$$

all remaining factor pairs would already have been examined in reverse order.

The implementation avoids redundant work with:

while divisor * divisor >= palindrome:

This optimization significantly improves performance and is essential for larger values of n.