Skip to content

906. Super Palindromes

Difficulty Topics

Description

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 1:

Input: left = "4", right = "1000"
Output: 4
Explanation: 4, 9, 121, and 484 are superpalindromes.
Note that 676 is not a superpalindrome: 26 * 26 = 676, but 26 is not a palindrome.

Example 2:

Input: left = "1", right = "2"
Output: 1

 

Constraints:

  • 1 <= left.length, right.length <= 18
  • left and right consist of only digits.
  • left and right cannot have leading zeros.
  • left and right represent integers in the range [1, 1018 - 1].
  • left is less than or equal to right.

Solution

super-palindromes.py
class Solution:
    def superpalindromesInRange(self, left: str, right: str) -> int:
        left = int(left)
        right = int(right)

        res = [1,2,3,4,5,6,7,8,9]

        for i in range(1, 10000):
            s = int(str(i) + str(i)[::-1])
            res.append(s)

            for j in range(10):
                res.append(int(str(i) + str(j) + str(i)[::-1]))

        def isPalindrome(s):
            return s == s[::-1]

        count = 0

        for val in res:
            s = val * val

            if left <= s <= right and isPalindrome(str(s)):
                count += 1

        return count