Skip to content

479. Largest Palindrome Product

Description

Given an integer n, return the largest palindromic integer that can be represented as the product of two n-digits integers. Since the answer can be very large, return it modulo 1337.

 

Example 1:

Input: n = 2
Output: 987
Explanation: 99 x 91 = 9009, 9009 % 1337 = 987

Example 2:

Input: n = 1
Output: 9

 

Constraints:

  • 1 <= n <= 8

Solutions

Solution 1

Thinking

The largest palindrome that is a product of two \(n\)-digit integers, modulo \(1337\). \(n\le 8\), so listing every product is heavy.

Enumerate the first half \(a\) downward, mirror it to a palindrome \(x\), and test for an \(n\)-digit factor \(t\) (from \(10^n-1\) down while \(t^2\ge x\)). The first hit is the maximum.

Building palindromes first meets the largest candidates sooner than enumerating products. \(n=1\) falls through to \(9\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def largestPalindrome(self, n: int) -> int:
        mx = 10**n - 1
        for a in range(mx, mx // 10, -1):
            b = x = a
            while b:
                x = x * 10 + b % 10
                b //= 10
            t = mx
            while t * t >= x:
                if x % t == 0:
                    return x % 1337
                t -= 1
        return 9

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int largestPalindrome(int n) {
        int mx = (int) Math.pow(10, n) - 1;
        for (int a = mx; a > mx / 10; --a) {
            int b = a;
            long x = a;
            while (b != 0) {
                x = x * 10 + b % 10;
                b /= 10;
            }
            for (long t = mx; t * t >= x; --t) {
                if (x % t == 0) {
                    return (int) (x % 1337);
                }
            }
        }
        return 9;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int largestPalindrome(int n) {
        int mx = pow(10, n) - 1;
        for (int a = mx; a > mx / 10; --a) {
            int b = a;
            long x = a;
            while (b) {
                x = x * 10 + b % 10;
                b /= 10;
            }
            for (long t = mx; t * t >= x; --t)
                if (x % t == 0)
                    return x % 1337;
        }
        return 9;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func largestPalindrome(n int) int {
    mx := int(math.Pow10(n)) - 1
    for a := mx; a > mx/10; a-- {
        x := a
        for b := a; b != 0; b /= 10 {
            x = x*10 + b%10
        }
        for t := mx; t*t >= x; t-- {
            if x%t == 0 {
                return x % 1337
            }
        }
    }
    return 9
}

Comments