largest-palindrome-product

Largest Palindrome Product – LeetCode 479

Problem

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.

Note:

The range of n is [1,8].

Example

Input: 2

Output: 987

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

Answer

Original

Code

class Solution {
public:
    int largestPalindrome(int n) {
        if (n == 1) return 9;
        int upper = pow(10, n) - 1;
        int lower = pow(10, n-1);
        for (int i = upper; i >= lower; i--) {
            long cand = buildPalindrome(i);
            for (long j = upper; j*j >= cand; j--) {
                if (cand % j == 0 && cand / j <= upper) {
                    return cand % 1337;
                }
            }
        }
        return -1;
    }
    
    long buildPalindrome(int n) {
        string s = to_string(n);
        reverse(s.begin(), s.end());
        return stol(to_string(n) + s);
    }
};

思路

先构造再验证。
耗时$401$ ms，排名$42.99\%$

Better

思路

直接打表，无话可说。
耗时$2$ ms，排名$6.69\%$

Code

class Solution {
public:
    int largestPalindrome(int n) {
        long long ret[8] = {9, 9009, 906609, 99000099, 9966006699, 999000000999, 99956644665999, 9999000000009999};
        return ret[n - 1] % 1337;
    }
};