LargestPalindromeProduct [source code]

public class LargestPalindromeProduct {
static
/******************************************************************************/
public class Solution {
    public int largestPalindrome(int n) {
        int ceiling = (int) Math.pow(10, n) - 1, floor = (int) Math.pow(10, n - 1);
        long max = 0;
        for (int i = ceiling; i >= floor; i--) {
            for (int j = ceiling; j >= floor; j--) {
                long prod = (long) i * j;
                if (isPalindrome(prod)) {
                    if (prod > max)
                        max = prod;
                }
            }
        }
        return (int) max % 1337;
    }

    public boolean isPalindrome(long n) {
        String str = Long.toString(n);
        return str.equals(new StringBuilder(str).reverse().toString());
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        LargestPalindromeProduct.Solution tester = new LargestPalindromeProduct.Solution();
        int[] inputs = {
            2, 987,
            1, 9,
            3, 123, 
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            int n = inputs[2 * i];
            int expected = inputs[1 + 2 * i];
            System.out.println(Printer.seperator());
            int output = tester.largestPalindrome(n);
            System.out.println(Printer.wrapColor(n + "", "magenta") + " -> " + output + Printer.wrapColor(", expected: " + expected, (expected == output ? "green" : "red")));
        }
    }
}

这个题目暂时也想不到什么特别好的办法了, 就直接穷搜了; 估计最后还是会超时;

穷搜的方法大概就是这么做了, 其他剩下的优化无非就是把isPalindrome再优化一下, 不过这个速度基本也就这样了; 这个做法在n是4的时候就已经超时了;

然后把isPalindrome优化了一下: 使用之前题目给出的最优解; 最后在5的时候还是超时了;

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

Difficulty:Easy
Total Accepted:3.2K
Total Submissions:16.1K
Contributor: arash2012
Companies
yahoo