Super Palindromes

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, 10^18 - 1].
• left is less than or equal to right.

class Solution:
    def superpalindromesInRange(self, left: str, right: str) -> int:
        L = int(left)
        R = int(right)
        MAGIC = 10**5

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

        count = 0

        # Generate odd length palindromes
        for i in range(1, MAGIC):
            s = str(i)
            palindrome = s + s[:-1][::-1]
            num = int(palindrome) ** 2
            if num > R:
                break
            if num >= L and is_palindrome(str(num)):
                count += 1

        # Generate even length palindromes
        for i in range(1, MAGIC):
            s = str(i)
            palindrome = s + s[::-1]
            num = int(palindrome) ** 2
            if num > R:
                break
            if num >= L and is_palindrome(str(num)):
                count += 1

        return count

Explanation:

The problem asks us to find the number of super-palindromes within a given range [left, right]. A super-palindrome is a number that is both a palindrome itself and the square of another palindrome.

The core idea is to generate palindromes and check if their squares are also palindromes and fall within the given range.

1. Generate Palindromes:
   • Since the input range can be up to 10¹⁸, the square root of the numbers in the range can be up to 10⁹. Therefore, we need to generate palindromes up to around 10⁹. However, we can optimize this by generating palindromes up to 10⁵ and then squaring them to check if they lie in the range.
   • We generate both odd-length and even-length palindromes.
   • To create odd-length palindromes, we take a number i (e.g., 123) and concatenate it with its reverse excluding the last digit (e.g., 12321).
   • To create even-length palindromes, we take a number i (e.g., 123) and concatenate it with its reverse (e.g., 123321).
2. Check for Super-palindrome Property:
   • For each generated palindrome, we square it.
   • If the square is within the range [left, right], we check if it's a palindrome itself.
   • If it is, we increment the count.

Example:

Let's say left = "4" and right = "1000".

1. We generate palindromes:
   • Odd length: 1, 2, 3, ..., 9, 11, 22, ...
   • Even length: 11, 22, 33, ..., 121, 131, ...
2. We square them and check if the result is in the range [4, 1000] and also a palindrome:
   • 1² = 1 (not in range)
   • 2² = 4 (in range, palindrome)
   • 3² = 9 (in range, palindrome)
   • 11² = 121 (in range, palindrome)
   • 22² = 484 (in range, palindrome)
   • ... other palindromes that square to > 1000

Therefore, the super-palindromes in the range [4, 1000] are 4, 9, 121, and 484. The function should return 4.

Big O Runtime Analysis O(MAGIC) where MAGIC is 10^5. Because the loops run from 1 to MAGIC, and inside the loops, the palindrome and is_palindrome functions take O(len(s)) and O(len(num)) respectively which are bounded by a constant. So the overall time complexity is O(MAGIC).

Big O Space Analysis O(1) - The space used by the algorithm is constant. This is because we are only using a few variables to store intermediate values and the count of super-palindromes. We are not using any data structures that scale with the input size.

Edge Cases

• Large Input Range: The input range can be very large (up to 10¹⁸). We handle this by generating palindromes up to a much smaller value (10⁵) and then squaring them.
• Zero: The problem specifies positive integers, so we don't need to handle zero.
• Single-Digit Inputs: The input can be a single-digit number. The code handles this case correctly.
• Perfect Square Boundary: The boundaries left and right can be perfect squares. The code handles this correctly.
• left and right are Equal: if left and right are equal, then the code functions correctly and returns 1 or 0 depending on whether the single number in the range is a super palindrome.