906. Super Palindromes

Problem Description

A super-palindrome is a number that is both a palindrome and the square of a palindrome. Given two numbers left and right (as strings), find the number of super-palindromes in the inclusive range [left, right].

Solution: Preprocessing and Enumeration

This solution leverages the fact that super-palindromes are squares of palindromic numbers. We can efficiently generate potential candidates and then check if they meet the criteria.

Approach:

1. Generate Palindromes: We generate palindromic numbers up to a certain limit. Since the square of a number in the range [1, 10^9) will be less than 10^18, which is the upper bound for our input, we generate palindromes up to 10^5. We can construct these palindromes by taking a number, reversing it, and concatenating the reverse to the original (handling even and odd lengths separately).

2. Calculate Squares: We calculate the square of each generated palindrome.

3. Check for Super-Palindromes: For each square, we check:

   • If it's within the range [left, right].
   • If it's a palindrome itself. (We use a helper function is_palindrome for this).

4. Count Super-Palindromes: We increment a counter for each number that satisfies both conditions.

Time Complexity: O(M1/4 log M), where M is the upper bound of the input range (approximately 1018). This is because we generate approximately M1/4 palindromes, and checking if a number is a palindrome takes O(log M) time.

Space Complexity: O(M1/4) to store the generated palindromes.

Code Implementation (Python)

ps = []
for i in range(1, 10**5 + 1):
    s = str(i)
    t1 = s[::-1]
    t2 = s[:-1][::-1]  #Handle even and odd length palindromes
    ps.append(int(s + t1))
    ps.append(int(s + t2))
 
def is_palindrome(x: int) -> bool:
    return str(x) == str(x)[::-1]
 
class Solution:
    def superpalindromesInRange(self, left: str, right: str) -> int:
        l, r = int(left), int(right)
        count = sum(1 for x in map(lambda x: x * x, ps) if l <= x <= r and is_palindrome(x))
        return count

Code Implementation (Java)

class Solution {
    private static long[] ps = new long[200000];
    static{
        int k=0;
        for(long i=1;i<=100000;i++){
            String s = String.valueOf(i);
            String rs = new StringBuilder(s).reverse().toString();
            ps[k++] = Long.parseLong(s+rs);
            String rs2 = new StringBuilder(s.substring(0,s.length()-1)).reverse().toString();
            ps[k++] = Long.parseLong(s+rs2);
        }
    }
    private boolean isPalindrome(long n){
        String s = String.valueOf(n);
        String rs = new StringBuilder(s).reverse().toString();
        return s.equals(rs);
    }
    public int superpalindromesInRange(String left, String right) {
        long l = Long.parseLong(left);
        long r = Long.parseLong(right);
        int count=0;
        for(long p: ps){
            long sq = p*p;
            if(sq>=l && sq<=r && isPalindrome(sq)) count++;
        }
        return count;
    }
}

Other Languages: The approach remains consistent across other languages (C++, Go, TypeScript). The primary difference would be in the syntax and data structures used. The core logic of generating palindromes, calculating squares, and checking for palindromes remains the same.