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

    public class Palindrome {
        public static void main(String[] args) {
            for (int n = 1; n <= 8; n++) {
                System.out.println(Solution.largestPalindrome(n));
            }
        }

        public static class Solution {
            public static int largestPalindrome(int n) {
                if (n == 1) {
                    return 9;
                }
                int high = (int) Math.pow(10D, n * 1D) - 1;
                int low = high / 10;
                for (int i = high; i > low; i--) {
                    long palindrome = getPalindrome(i);
                    for (long j = high; j > low; j--) {
                        if (palindrome / j > high) {
                            break;
                        }
                        if (palindrome % j == 0) {
                            return (int) (palindrome % 1337);
                        }
                    }
                }
                return -1;
            }

            private static long getPalindrome(int num) {
                return Long.parseLong(num + (new StringBuilder(String.valueOf(num))).reverse().toString());
            }
        }

    }