Formatted question description: https://leetcode.ca/all/479.html

479. Largest Palindrome Product

Level

Hard

Description

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].

Solution

If n is 1, return 9. For n greater than 1, the maximum n-digit number is 10^n - 1. For each n-digit number, create a palindrome that has 2 * n digits and check whether there exists an n-digit number that is greater than or equal to the palindrome’s square root and can divide the palindrome completely. If such an n-digit number is found, return the palindrome mod 1337.

class Solution {
    public int largestPalindrome(int n) {
        if (n == 1)
            return 9;
        long max = (long) Math.pow(10, n) - 1;
        long start = max - 1, end = max / 10 + 1;
        for (long i = max - 1; i >= end; i--) {
            String str = String.valueOf(i);
            StringBuffer sb = new StringBuffer(str).reverse();
            long palindrome = Long.parseLong(str + sb.toString());
            long min = (long) Math.ceil(Math.sqrt(palindrome));
            for (long j = max; j >= min; j--) {
                if (palindrome % j == 0)
                    return (int) (palindrome % 1337);
            }
        }
        return -1;
    }
}

All Problems

All Solutions