Largest Palindrome Product Python Solution

lcpy gen -n 479   # by problem number
lcpy gen -s largest_palindrome_product   # by problem name

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

Input: n = 1
Output: 9

class Solution:
    # Time: O(10^n) over the first half, each candidate factorized in O(10^(n/2))
    # Space: O(1)
    def largest_palindrome(self, n: int) -> int:
        if n == 1:
            return 9
        upper = 10**n - 1
        lower = 10 ** (n - 1)
        for half in range(upper, lower - 1, -1):
            s = str(half)
            cand = int(s + s[::-1])
            factor = upper
            while factor * factor >= cand:
                if cand % factor == 0:
                    return cand % 1337
                factor -= 1
        raise AssertionError("no palindrome found")