Problem Description

A super-palindrome is defined as a positive integer that satisfies two conditions:

1. It is a palindrome (reads the same forwards and backwards)
2. It is the square of a palindrome

Given two positive integers left and right (represented as strings), you need to count how many super-palindromes exist in the inclusive range [left, right].

For example:

• 9 is a super-palindrome because:

  • 9 is a palindrome
  • 9 = 3², and 3 is also a palindrome

• 484 is a super-palindrome because:

  • 484 is a palindrome
  • 484 = 22², and 22 is also a palindrome

The task is to find all such numbers within the given range and return the count.

Intuition

The key insight is recognizing that checking every number in the range [left, right] would be inefficient, especially since the range can be as large as 10^18. Instead, we should work backwards from the definition of super-palindromes.

Since a super-palindrome must be the square of a palindrome, we can generate palindromes first, square them, and then check if the result is also a palindrome and falls within our range. This dramatically reduces the search space.

Given that the maximum value is around 10^18, the maximum palindrome whose square could be a super-palindrome is approximately √(10^18) = 10^9. However, we need to generate palindromes efficiently.

To generate palindromes systematically, we can use a clever technique: take the first half of the palindrome and mirror it. For any number i, we can create two types of palindromes:

1. Even-length palindrome: Mirror the entire number. For example, from 123 we get 123321
2. Odd-length palindrome: Mirror all but the last digit. For example, from 123 we get 12321

Since we're looking for palindromes up to 10^9, and palindromes are generated by mirroring their first half, we only need to iterate through numbers up to about 10^5 (since mirroring a 5-digit number gives us up to a 10-digit palindrome).

The preprocessing step generates all possible palindromes by iterating through i from 1 to 10^5, creating both even and odd-length palindromes from each i. Then, for each palindrome p in our precomputed list, we:

1. Calculate p²
2. Check if p² is within the range [left, right]
3. Check if p² is itself a palindrome

This approach is much more efficient than brute force because we're only checking the squares of palindromes rather than all numbers in the potentially massive range.

Learn more about Math patterns.

Solution Approach

The solution consists of two main parts: preprocessing palindromes and checking for super-palindromes.

Step 1: Generate All Palindromes (Preprocessing)

We iterate through numbers from 1 to 10^5 and generate palindromes:

for i in range(1, 10**5 + 1):
    s = str(i)
    t1 = s[::-1]  # Reverse of the entire string
    t2 = s[:-1][::-1]  # Reverse of string without last character
    ps.append(int(s + t1))  # Even-length palindrome
    ps.append(int(s + t2))  # Odd-length palindrome

For example, when i = 123:

• s + t1 creates "123" + "321" = "123321" (even-length)
• s + t2 creates "123" + "21" = "12321" (odd-length)

This generates all palindromes up to approximately 10^10, which when squared can reach up to 10^20, covering our required range.

Step 2: Check if a Number is a Palindrome

The helper function efficiently checks palindrome without string conversion:

def is_palindrome(x: int) -> bool:
    y, t = 0, x
    while t:
        y = y * 10 + t % 10
        t //= 10
    return x == y

This function reverses the number mathematically:

• Extract the last digit using t % 10
• Build the reversed number by multiplying y by 10 and adding the digit
• Remove the last digit from t using integer division

Step 3: Count Super-Palindromes

l, r = int(left), int(right)
return sum(l <= x <= r and is_palindrome(x) for x in map(lambda x: x * x, ps))

For each palindrome p in our precomputed list ps:

1. Calculate x = p² using map(lambda x: x * x, ps)
2. Check if x is within the range [l, r]
3. Check if x itself is a palindrome using is_palindrome(x)
4. Count all numbers satisfying both conditions

Time Complexity: O(M^(1/4) × log M) where M is the upper bound (10^18). We generate O(M^(1/4)) palindromes, and for each palindrome's square, we check if it's a palindrome in O(log M) time.

Space Complexity: O(M^(1/4)) to store all the generated palindromes in the list ps.

Example Walkthrough

Let's walk through finding super-palindromes in the range [4, 1000].

Step 1: Generate palindromes

Starting with small values of i:

When i = 1:

• Even-length: "1" + "1" = "11" → palindrome = 11
• Odd-length: "1" + "" = "1" → palindrome = 1

When i = 2:

• Even-length: "2" + "2" = "22" → palindrome = 22
• Odd-length: "2" + "" = "2" → palindrome = 2

When i = 3:

• Even-length: "3" + "3" = "33" → palindrome = 33
• Odd-length: "3" + "" = "3" → palindrome = 3

When i = 10:

• Even-length: "10" + "01" = "1001" → palindrome = 1001
• Odd-length: "10" + "0" = "100" → palindrome = 100 (not a palindrome, but we still include it)

When i = 11:

• Even-length: "11" + "11" = "1111" → palindrome = 1111
• Odd-length: "11" + "1" = "111" → palindrome = 111

We continue this process up to i = 10^5, building our list ps = [1, 1, 11, 2, 22, 2, 33, 3, ...]

Step 2: Check each palindrome's square

For each palindrome in ps, we square it and check:

• 1² = 1: Is 1 in [4, 1000]? No → skip
• 2² = 4: Is 4 in [4, 1000]? Yes → Is 4 a palindrome? Yes → Count it!
• 3² = 9: Is 9 in [4, 1000]? Yes → Is 9 a palindrome? Yes → Count it!
• 11² = 121: Is 121 in [4, 1000]? Yes → Is 121 a palindrome? Yes → Count it!
• 22² = 484: Is 484 in [4, 1000]? Yes → Is 484 a palindrome? Yes → Count it!
• 33² = 1089: Is 1089 in [4, 1000]? No → skip
• 100² = 10000: Is 10000 in [4, 1000]? No → skip
• 111² = 12321: Is 12321 in [4, 1000]? No → skip

Step 3: Verify palindrome check for 484

Using the is_palindrome function on 484:

• Initialize: y = 0, t = 484
• Iteration 1: y = 0 * 10 + 4 = 4, t = 48
• Iteration 2: y = 4 * 10 + 8 = 48, t = 4
• Iteration 3: y = 48 * 10 + 4 = 484, t = 0
• Compare: 484 == 484 → True, it's a palindrome!

Result: In the range [4, 1000], we found 4 super-palindromes: 4, 9, 121, 484

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n = 10^5

The preprocessing step iterates through numbers from 1 to 10^5, and for each number:

• String conversion takes O(log i) time
• String reversal takes O(log i) time
• Creating palindromes takes O(log i) time
• Total preprocessing: O(n * log n)

For the main function:

• Converting left and right strings to integers: O(1) (assuming fixed-length input)
• Iterating through all palindromes in ps (which has 2 * 10^5 elements): O(n)
• For each palindrome, computing x * x: O(1)
• Checking if x is in range: O(1)
• is_palindrome function: O(log x) where x can be up to (10^10)^2 = 10^20, so O(20) = O(1)
• Total main function: O(n)

Overall time complexity: O(n * log n) for preprocessing + O(n) for query = O(n * log n)

Since preprocessing happens once and n = 10^5 is constant, this simplifies to O(1) amortized per query.

Space Complexity: O(n) where n = 10^5

• The ps list stores 2 * 10^5 palindrome numbers: O(n)
• The is_palindrome function uses O(1) auxiliary space
• Other variables use O(1) space

Total space complexity: O(n) = O(10^5) = O(1) since it's a fixed constant.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow When Squaring Large Palindromes

The most critical pitfall in this solution is potential integer overflow. When generating palindromes up to 10^5, the resulting palindromes can be as large as 10^10. When squared, these values can reach 10^20, which exceeds the maximum value for standard 32-bit integers and even approaches the limits of 64-bit integers in some languages.

Problem Example:

# A palindrome like 9999999999 (10 digits)
# When squared: 9999999999^2 = 99999999980000000001 (20 digits)
# This could cause overflow in languages with fixed integer sizes

Solution:

• In Python, this isn't an issue since integers have arbitrary precision
• In other languages like Java or C++, use long long or BigInteger
• Add boundary checks before squaring to prevent overflow

2. Inefficient Palindrome Generation Bounds

Generating palindromes up to 10^5 creates many unnecessary palindromes whose squares will far exceed the typical input range. This wastes memory and computation time.

Problem Example:

# If right = "1000000000" (10^9), we only need palindromes up to sqrt(10^9) ≈ 31623
# But we're generating palindromes up to 10^10, most of which are unnecessary

Solution:

def superpalindromesInRange(self, left: str, right: str) -> int:
    right_bound = int(right)
    # Calculate the maximum palindrome we need to check
    max_palindrome_needed = int(right_bound ** 0.5) + 1
  
    # Generate palindromes only up to what's needed
    palindrome_roots = []
    limit = min(10**5, max_palindrome_needed)
    for num in range(1, limit + 1):
        # ... rest of palindrome generation

3. Duplicate Palindromes in the List

The current generation method can create duplicate palindromes, especially for small numbers.

Problem Example:

# When num = 1:
# odd_palindrome: "1" + "1" = "11"
# even_palindrome: "1" + "" = "1"
# When num = 11:
# odd_palindrome: "11" + "11" = "1111"
# even_palindrome: "11" + "1" = "111"
# But "111" might be generated again from num = 111

Solution:

# Use a set to store palindromes and avoid duplicates
palindrome_roots = set()
for num in range(1, 10**5 + 1):
    num_str = str(num)
    palindrome_roots.add(int(num_str + num_str[::-1]))
    palindrome_roots.add(int(num_str + num_str[:-1][::-1]))
palindrome_roots = sorted(list(palindrome_roots))

4. Edge Case: Single-Digit Numbers

The palindrome generation might miss single-digit numbers (1-9), which are palindromes themselves and some of which have palindromic squares.

Problem Example:

# Numbers 1, 4, 9 are super-palindromes (1^2=1, 2^2=4, 3^2=9)
# The current generation starts from num=1 but creates "11" and "1"
# It might miss handling these edge cases properly

Solution:

# Explicitly include single-digit palindromes
palindrome_roots = list(range(1, 10))  # Start with 1-9
for num in range(1, 10**5 + 1):
    # ... continue with regular generation

5. String Slicing Index Error

When creating even-length palindromes with num_str[:-1][::-1], if num_str has only one character, num_str[:-1] becomes an empty string.

Problem Example:

# When num = 1 through 9:
# num_str = "1", num_str[:-1] = "" (empty string)
# This creates the same palindrome twice: "1" + "" = "1"

Solution:

for num in range(1, 10**5 + 1):
    num_str = str(num)
    palindrome_roots.append(int(num_str + num_str[::-1]))
    if len(num_str) > 1:  # Only create even-length if meaningful
        palindrome_roots.append(int(num_str + num_str[:-1][::-1]))