Problem statement

https://leetcode.com/problems/largest-palindrome-product/

Solution 1

Interesting problem with is almost purely mathematical. There is brute-force approach, which is to start from the biggest possible palindrome and try to find its divisors, which are more than square root of it.

Complexity

It is difficult to estimate, I think something between O(10^(n/2)) and O(10^n)`.

Code

class Solution:
    def largestPalindrome(self, n):
        if n == 1: return 9
        cand = 10**n-1
        while True:
            Number = int(str(cand) + str(cand)[::-1])
            root = math.ceil(math.sqrt(Number))
            for div in range(root, 10**n):
                if Number % div == 0:
                    return Number % 1337
            cand -= 1

Solution 2

There is smarter mathematical solution. Let our palindrome be equal to $U\cdot 10^n\cdot U + L = (10^n - a)(10^n - b)$, where $U$ is reverse of $L$ and $a$ and $b$ are potentially small numbers. This leads to $(a+b-10^n+U)\cdot 10^n = ab - L$. We can assume that $a+b = 10^n - U$ and $ab = L$ if $n$ is big enough (why though, I fail to prove). Then we can solve this quadratic equation, given $U$ and $L$ and check if it has roots.

Complexity

It is faster than previous approach, but again difficult to say, I should say around O(10^(n/2)).

Code

class Solution(object):
    def largestPalindrome(self, n):
        if n <= 2: return [9,987][n-1]

        for a in range(2, 10**n):
            hi = (10**n)-a
            lo = int(str(hi)[::-1])
            cand = a*a - 4*lo
            if cand < 0: continue
            if math.sqrt(cand) == int(math.sqrt(cand)):
                return int(str(hi)+str(hi)[::-1]) % 1337