479. Largest Palindrome Product 最大回文数乘积

@TOC

# 题目描述

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

# 解题方法

``````class Solution(object):
def largestPalindrome(self, n):
if n==1: return 9
if n==2: return 987
for a in xrange(2, 9*10**(n-1)):
hi=(10**n)-a
lo=int(str(hi)[::-1])
if a**2-4*lo < 0: continue
if (a**2-4*lo)**.5 == int((a**2-4*lo)**.5):
return (lo+10**n*(10**n-a))%1337
``````

``````class Solution(object):
def largestPalindrome(self, n):
"""
:type n: int
:rtype: int
"""
upper = 10 ** n - 1
lower = upper / 10
for i in xrange(upper, lower, -1):
l = int(str(i) + str(i)[::-1])
j = upper
while j * j > l:
if l % j == 0:
return l % 1337
j -= 1
return 9
``````

C++代码效率比较高，能通过。

``````class Solution {
public:
int largestPalindrome(int n) {
int upper = pow(10, n) - 1;
int lower = upper / 10;
for (int i = upper; i > lower; i--){
string s = to_string(i);
long p = stol(s + string(s.rbegin(), s.rend()));
for (long j = upper; j * j > p; j--){
if (p % j == 0){
return p % 1337;
}
}
}
return 9;
}
};
``````

# 日期

2018 年 2 月 28 日 2018 年 11 月 30 日 —— 又到了周末