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: 2Output: 987Explanation: 99 x 91 = 9009, 9009 % 1337 = 987Note:The range of n is [1,8].

Solution

从合适位置开始, 合适位置结束, 暴力搜索

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 long cand = creatPalindrome(i);            for (int j = upper; cand / j < j; --j) {                if (cand % j == 0) return cand % 1337;            }        }        return -1;    }private:    long long creatPalindrome(int n) {        string lastHalf = to_string(n);        reverse(lastHalf.begin(), lastHalf.end());        return stoll(to_string(n) + lastHalf);    }};