Super Palindromes — LeetCode 906 Python Solution

The problem

Let's say a positive integer is a super-palindrome if it is a palindrome, and it is also the square of a palindrome. Given two positive integers left and right represented as strings, return the number of super-palindromes integers in the inclusive range [left, right].

Example

Input

left = "4", right = "1000"

Output

4

Explanation

4, 9, 121, and 484 are superpalindromes.

Python solution

ps = []
for i in range(1, 10**5 + 1):
    s = str(i)
    t1 = s[::-1]
    t2 = s[:-1][::-1]
    ps.append(int(s + t1))
    ps.append(int(s + t2))


class Solution:
    def superpalindromesInRange(self, left: str, right: str) -> int:
        def is_palindrome(x: int) -> bool:
            y, t = 0, x
            while t:
                y = y * 10 + t % 10
                t //= 10
            return x == y

        l, r = int(left), int(right)
        return sum(l <= x <= r and is_palindrome(x) for x in map(lambda x: x * x, ps))

Complexity

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 906. Super Palindromes is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Math.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Related problems