479. Largest Palindrome Product

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

package l479; /* * 面试场上正常情况应该就是用brute force，就是做点优化 * 关键在于快速的寻找下一个回文数字，然后判断是不是可以写成2个数的乘积 * * 从小到大的回文数字是： * 9889，9779,9669,9559，。。。。 * 所以就只要关注前2个数字 */ public class Solution { public int largestPalindrome(int n) { if(n == 1) return 9; int maxHalf = (int) (Math.pow(10, n)-1); for(int i=maxHalf-1; i>maxHalf/10; i--) { long max = Long.valueOf(i + new StringBuilder().append(i).reverse().toString()); //判断这个max是否是 2个数的乘积 for(long j=maxHalf; j*j>=max; j--) if(max % j == 0) return (int) (max37); } return -1; } }