原题链接在这里：https://leetcode.com/problems/largest-palindrome-product/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].
题解：
当n=2时，数字可选区间就是(9, 99]. 最大的product 就是 99*99 = 9801. 最大的位数是2n 肯定是个偶数.
取前一半firstHalf '98', 再拼接'98'的reverse '89'组成新的palindrome '9889'. 然后i在(9,99]之间挨个试palindrome % i == 0.
试不出来firstHalf--, 变'97'重来.
Time Complexity: O((upperBound*upperBound)/10^n * (upperBound*lowerBound)), upperBound = 10^n, lowerBound = upperBound/10.
Space: O(1).
AC Java:
class Solution {
public int largestPalindrome(int n) {
if(n == 1){
return 9;
}
int upperBound = (int)Math.pow(10, n) - 1;
int lowerBound = upperBound/10;
long max = (long)upperBound * (long)upperBound;
int firstHalf = (int)(max/(long)Math.pow(10,n));
boolean palFound = false;
long pal = 0;
while(!palFound){
pal = createPal(firstHalf);
for(long i = upperBound;; i--){
if(pal/i>max || i*i<pal){
break;
}
if(pal%i == 0){
palFound = true;
break;
}
}
firstHalf--;
}
return (int)(pal%1337);
}
private long createPal(int n){
String s = n + new StringBuilder().append(n).reverse().toString();
return Long.valueOf(s);
}
}