LC 479 Largest Palindrome Product(M)

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

边界条件

解题思路

输入范围n∈[1, 8]，除n = 1以外，其余n值最大回文数palindrome的位数均为偶数，可以拆分为half与reversed(half)左右两半

从上界high = pow(10, n) - 1向下界low = pow(10, n - 1)枚举half，构造回文，检查是否存在两个n位数的除数

public int largestPalindrome(int n) {
    if(n == 1)
        return 9;
    int high = (int)Math.pow(10, n) -1;
    int low = high / 10;

    for(int i = high; i > low; i--){
        long palin= createPalindrome(i);

        for(int j = high; j > low; j--){
            int temp = (int)(palin / j);
            if(temp > high || temp < low){
                break;
            }
            if(palin % j ==0){
                return (int)(palin % 1337);
            }
        }
    }
    return -1;
}
public long createPalindrome(int num){
    String value = num + new StringBuilder(Long.toString(num)).reverse().toString();
    return Long.parseLong(value);
}