We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Super Palindromes

Difficulty: Hard

Problem Description

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].

Key Insights

  • A super-palindrome must be both a palindrome and the square of another palindrome.
  • The range of numbers can be very large (up to 10^18), so we need an efficient way to check for super-palindromes.
  • We can generate palindromes and check their squares to see if they fall within the given range.

Space and Time Complexity

Time Complexity: O(n), where n is the number of palindromes we generate and check. Space Complexity: O(1), as we only use a fixed amount of space for variables.

Solution

To solve the problem, we can follow these steps:

  1. Generate all possible palindromic numbers up to a certain limit.
  2. For each palindromic number, calculate its square.
  3. Check if the squared value is a palindrome and falls within the given range [left, right].
  4. Count the valid super-palindromes.

We can use a loop to generate palindromes by constructing them from half of the digits, and then checking both even and odd lengths. The palindrome check can be done easily by converting the number to a string and comparing it with its reverse.

Code Solutions

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

def super_palindromes_in_range(left, right):
    left = int(left)
    right = int(right)
    count = 0
    
    # Generate palindromes and check their squares
    for i in range(1, 10**5):  # 10^5 is chosen as it covers up to 10^18 when squared
        p1 = int(str(i))  # Odd-length palindrome
        p2 = int(str(i) + str(i)[::-1])  # Even-length palindrome
        
        for p in [p1, p2]:
            square = p * p
            if square > right:
                break
            if square >= left and is_palindrome(square):
                count += 1
                
    return count

# Example usage
print(super_palindromes_in_range("4", "1000"))  # Output: 4
← Back to All Questions