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

解法1：

这题不认为是简单题。。。
主要的思路是，对于一个n位的数字，最大的数字就是pow(10, n) - 1, 那么可以从这个数字开始，计算出最大的可能的乘积。
这就确定了我们搜索的上边界，那么如果把这个数分成左右两半，我们可以把左面的数看成是乘积左面的上边界然后遍历他，直到左面的数小于n个数字。
然后每次对左面的数减1，看是否能构造成两个满足是palindrome的数。
对于拆分成左右两个数，用到了left = prod / mod 和right = prod % mod的办法，其中mod = pow(10, n)
也就是说，对于2位的数，最大可能乘积为4位，那么pow(10,2) = 100，4位的 mod 100可以得到后面两位，左面同理。
对于每一个left的数，构造出一个palindrome的数，然后去看是否满足这个数能被其中一个数整除（范围是[i, prod/i]),其中i从maxNumber开始。

C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class Solution {
    public int largestPalindrome(int n) {
        if (n == 1) {
            return 9;
        }
        int base = 1337;
        int mod = (int)Math.pow(10, n);
        int maxNumber = (int)Math.pow(10, n) - 1;   // Start from maxNumber and traverse until a result is found
        long prod = (long)maxNumber * (long)maxNumber;
        // To split prod into left half and right half
        int left = (int)(prod / mod);  
        int right = (int)(prod % mod);
        if (left == reverse(right)) return (int)(prod % base);
        left--;
        prod = (long)left * (long)mod + (long)reverse(left);
        // Traverse from left to min
        while (left != mod / 10) {
            for (int i = maxNumber; i > prod / i; i--) {
                if (prod % i == 0) {
                    return (int)(prod % base);
                }
            }
            left--;
            prod = (long)left * (long)mod + (long)reverse(left);
        }
        return (int)(prod % base);
    }
    private int reverse(int n) {
        int x = n;
        int res = 0;
        while (x != 0) {
            res = res * 10 + (x % 10);
            x /= 10;
        }
        return res;
    }
}