479. Largest Palindrome Product

Description

image-20210825130538679

Solution

Because two n-digits intergers’ product are range from 2n-1 digits to 2n digits. Our strategy is constructing palindrome by str + reverse(str) . Then we detect from highest n-digits interger to sqrt(palin) to see if it can be divided into 2 n digits numbers.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def largestPalindrome(self, n: int) -> int:
        def getPalin(i):
            s = str(i)
            s += s[::-1]
            return int(s)
        if n==1:
            return 9
        low = pow(10,n-1)
        high = pow(10,n)-1
        for i in range(high,low-1,-1):
            p = getPalin(i)
            for j in range(high, int(sqrt(p)), -1):
                if p % j == 0 and p / j >= low:
                    return p % 1337
        return -1