479. Largest Palindrome Product

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

-----------------------
又恶心！
Solution#1, 找出上下边界，做遍历。超时
Solution#2 在上下边界内遍历所有的palindrome，找出符合的

class Solution {
    public int largestPalindrome(int n) {
        if (n == 1) return 9;
        
        long upper = (long)Math.pow(10, n) - 1;
        long lower = (long)Math.pow(10, n - 1);
        long max = (long)upper * (long)upper;        
        long firstHalf = max / (long)Math.pow(10, n);
        
        boolean found = false;
        long pal = 0;
        while (!found) {
            pal = createPal(firstHalf);
            for (long i = upper; i >= lower; i--) {
                if (pal > i * i) break;
                if (pal % i == 0) {
                    found = true;
                    break;        
                }
            }
            firstHalf--;
        }
        
        return (int)(pal % 1337);
    }
    
    private long createPal(long firstHalf) {
        String s = firstHalf + new StringBuilder().append(firstHalf).reverse().toString();
        return Long.parseLong(s);
    }
}