Largest Palindrome Product

Question

Find the largest palindrome made from the product of two n-digit numbers.

Since the result could be very large, you should return the largest palindrome mod 1337.

Example:

Input: 2

Output: 987

Explanation: 99 x 91 = 9009, 9009 % 1337 = 987

Note:

The range of n is [1,8].

Tags

• Mathematics

Thought

Reference: http://bookshadow.com/weblog/2017/01/05/leetcode-largest-palindrome-product/

When selecting the approach for this problem, it should be careful, because the OJ for time limit is really strict. Here is the solution:

1. Corner case: n = 1, the result will be 9
2. Except for the corner case, the number of digits for the maximum palindrome number in other cases will always be even. Thus, we can split the palindrome number into half and reversed(half) parts.
3. We start to search from the upper bound until the lower bound for the half of the palindrome number. In the loop, we create the complete palindrome number according to the given half, then check whether it is a valid palindrome number. If, it is a valid palindrome number, we can stop the loop here and return the result.

Note: As I said, the time limit is strict here. Thus, the python implementation of this algorithm cannot pass the test, but the java implementation can pass the test.

Code

python version

class Solution(object):
    def createPalindrome(self, num):
        return int(num + num[::-1])

    def largestPalindrome(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
            return 9
        high = 10**n - 1
        low = high / 10

        for num in xrange(high, low, -1):
            palindrome = self.createPalindrome(str(num))
            for i in xrange(high, low, -1):
                if palindrome / i > high:
                    break
                if palindrome % i == 0:
                    return (palindrome % 1337)
        return -1

java version

public class Solution {
    public int largestPalindrome(int n) {
        if (n == 1) {
            return 9;
        }

        int high = (int) Math.pow(10, n) - 1, low = high / 10;

        for (int i = high; i > low; i--) {
            long palindrome = createPalindrome(i);

            for (long j = high; j > low; j--) {
                if (palindrome / j > high) {
                    break;
                }
                if (palindrome % j == 0) {
                    return (int) (palindrome % 1337);
                }
            }
        }
        return -1;
    }

    private long createPalindrome(long num) {
        String str = num + new StringBuilder(Long.toString(num)).reverse().toString();
        return Long.parseLong(str);
    }
}