Problem statement

https://leetcode.com/problems/super-palindromes/

Solution

It this problem we can use the fact, that number of super palindromes is not very big one. If we have superpalindrome X, then by definition X = Y*Y, where Y is also palindrome. Note also, that palindrome is defined by the first half Z of its digits, so if we consider all Z in region [1, W^0.25] it will be enough. Indeed, let us consider all Z in region [1, 10^5), it will be enough: in this case Y will be in range [1, 10^9) and X will be in range [1, 10^18).

So, what I did here is just precompute all palindromes and then use binary search to calculate number of them.

Complexity

Time complexity is O(W^0.25 * log W), where W = 10^18 is the upper limit. Here we have log W factor, because for each candidate we transfrom it to string and also becauswe we use sort in the end. Space complexity is O(W^0.25). Note also that in practice this will work quite fast, because we evaluate nums outside function, so it will be calculated only once.

from bisect import bisect

class Solution:
    nums = []
    for i in range(1, 100000):
        cand1 = int(str(i) + str(i)[::-1])**2
        cand2 = int(str(i)[:-1]  + str(i)[::-1])**2
        if str(cand1) == str(cand1)[::-1]: nums += [cand1]
        if str(cand2) == str(cand2)[::-1]: nums += [cand2]

    nums = sorted(list(set(nums)))

    def superpalindromesInRange(self, L, R):
        return bisect(self.nums, int(R)) - bisect(self.nums, int(L)-1)