Super Palindrome Solution

Problem Understanding

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 and the square of another palindrome.

Naive Approach

A naive approach would involve iterating through all numbers in the range [left, right], checking if each number is a palindrome, and if so, checking if its square root is also a palindrome. This approach is highly inefficient.

Code (Python - Naive):

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


def naive_superpalindromes_in_range(left, right):
    left_num = int(left)
    right_num = int(right)
    count = 0
    for i in range(left_num, right_num + 1):
        if is_palindrome(i):
            sqrt_i = i**0.5
            if sqrt_i == int(sqrt_i) and is_palindrome(int(sqrt_i)):
                count += 1
    return count

Time Complexity: O(N * sqrt(N)), where N is the size of the range (right - left + 1). Space Complexity: O(1)

Optimal Approach

Instead of checking every number in the range, we can generate palindromes and check if their squares are both within the range and are palindromes. Since the range is up to 10^18, the square root will be up to 10^9. We generate palindromes up to 10^9 and check their squares.

1. Generate Palindromes: Create palindromes by reflecting the first half of the number. Generate both even and odd length palindromes.
2. Square and Check: Square each generated palindrome. Check if the square falls within the given range and if it's also a palindrome.

Code (Python - Optimal):

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


def generate_palindromes():
    palindromes = []
    for i in range(1, 100000):
        s = str(i)
        pal1 = s + s[::-1]  # even length palindrome
        pal2 = s + s[:-1][::-1]  # odd length palindrome
        palindromes.append(int(pal1))
        palindromes.append(int(pal2))
    return palindromes


def superpalindromes_in_range(left, right):
    left_num = int(left)
    right_num = int(right)
    count = 0
    palindromes = generate_palindromes()
    for pal in palindromes:
        sq = pal * pal
        if left_num <= sq <= right_num and is_palindrome(sq):
            count += 1
    return count

Time Complexity: O(N), where N is the number of palindromes generated. Since we are generating palindromes up to 10^9, the number of palindromes generated is limited, making this approach much more efficient.

Space Complexity: O(N), where N is the number of palindromes generated. The space is used to store the list of generated palindromes.

Edge Cases

• Small Ranges: The range might be small (e.g., "1", "2"). The algorithm should still work correctly.
• Large Numbers: The input numbers can be large (up to 10^18). Use appropriate data types (e.g., long in Java, int in Python) to handle large numbers without overflow.
• Zero: The problem states positive integers so we don't need to worry about this.

Example

left = "4", right = "1000"

The algorithm will generate palindromes, square them, and check if they fall in the range [4, 1000] and are also palindromes. The super-palindromes in this range are 4 (2x2), 9 (3x3), 121 (11x11), and 484 (22x22). Therefore, the output is 4.