Super Palindromes - Leetcode Solution

Problem Statement:

A super palindrome is a palindrome that 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].

A palindrome is a word, number, phrase, or another sequence of characters that reads the same forward and backward ignoring spaces, capitalization, and punctuation. In simple words, it is a word that remains the same even if it is read backward.

Example 1:

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

Example 2:

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

Solution:

This problem can be solved by checking all the palindromes which are the square of some palindrome. We will start by generating all palindromic numbers less than the square root of the maximum possible palindrome (10^18). Since we are looking for square palindromes, we must square each of these palindromic numbers and evaluate whether they are less than or equal to the maximum value right.

We will iterate over all these square palindromes and check if they are palindromes themselves. If a square palindrome passes these tests, we count it as a super palindrome.

Algorithm:

1. Define a variable count to store the count of super palindromes.

2. Define a list palindrome to store all palindromes in the range 1 to (10^5) + 1.

3. For each number in palindrome, square it, and check if it is a palindrome itself.

4. If a square palindrome is less than or equal to right, check if it is in the range of left and right.

5. If a square palindrome is in the range of left and right, increment the count.

6. Return the count.

Python Code:

class Solution: def superpalindromesInRange(self, left: str, right: str) -> int:

    # Function to check if a number is a palindrome
    def is_palindrome(n):
        return str(n) == str(n)[::-1]
    
    # Generate all palindromic numbers less than the square root of the maximum possible palindrome
    palindrome = [1,2,3,4,5,6,7,8,9]
    for i in range(1,10000):
        s = str(i)
        palindrome.append(int(s+s[::-1]))
        for j in range(10):
            palindrome.append(int(s+str(j)+s[::-1]))
    
    # Check all square palindromes
    count = 0
    for p in palindrome:
        square = p*p
        if square > int(right):
            break
        if square >= int(left) and is_palindrome(square):
            count += 1
    
    return count

Complexity Analysis:

Time Complexity:

The time complexity of the above solution is O(n * log(n)) where n is the number of palindromic numbers generated. This is because we generate all palindromic numbers up to the square root of the maximum possible palindrome, which is about 10^9. We then iterate over each of these numbers and square them, which takes O(logn) time.

Space Complexity:

The space complexity of the above solution is O(n) where n is the number of palindromic numbers generated. We generate a list of palindromic numbers up to the square root of the maximum possible palindrome, which is about 10^9. Each number in this list takes up O(logn) space.

1