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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Super Palindromes

Number: 942

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given two positive integers left and right (as strings), count the number of integers in the inclusive range [left, right] that are super-palindromes. A super-palindrome is defined as an integer that is a palindrome and also the square of a palindrome.

Key Insights

  • The range for left and right can be huge (up to 10^18), however the potential candidate palindromic roots are limited by the square root of right.
  • Rather than iterating over all numbers in [left, right], generate palindromic numbers (which serve as potential roots) and then square them.
  • Both odd-length and even-length palindromes need to be generated as candidate roots.
  • For each candidate, square it and check if the result is a palindrome and falls within [left, right].

Space and Time Complexity

Time Complexity: O(X * log(P)) where X is the number of palindromic roots generated (bounded by roughly 10^5 candidate roots) and log(P) is the time to check if a number is a palindrome. Space Complexity: O(1) extra space (apart from the output and storage for candidate variables).

Solution

The solution generates candidate palindromic roots by constructing palindromes from half portions and then mirroring them to form full palindromes. Both odd-length and even-length fields are generated. For each candidate palindrome root, compute its square and check:

  1. That the square is within the range [left, right].
  2. That the square is itself a palindrome. The palindrome check is performed by converting the number to a string and comparing it with its reverse. This avoids iterating over the entire range [left, right] and leverages the fact that the number of palindromic roots up to sqrt(right) is small.

Code Solutions

# Python solution for Super Palindromes
def is_palindrome(num_str):
    # Check if a string is a palindrome by comparing it with its reverse
    return num_str == num_str[::-1]

def superpalindromesInRange(left: str, right: str) -> int:
    L = int(left)
    R = int(right)
    count = 0
    # The upper limit for the palindrome root is the square root of R.
    # Since R can be up to 10^18, max_root is approximately 10^9.
    # We generate palindromic roots by constructing them from half parts.
    
    # Upper bound for half length, 10^5 generates palindromes up to around 10^9.
    # Adjust this limit based on problem constraints.
    max_half = 100000
    
    # Generate odd-length palindromes.
    for k in range(1, max_half):
        s = str(k)
        t = s[-2::-1]  # Reverse all but the last digit for odd-length palindrome
        pal_str = s + t
        pal_num = int(pal_str)
        square = pal_num * pal_num
        if square > R:
            break
        if square >= L and is_palindrome(str(square)):
            count += 1
    
    # Generate even-length palindromes.
    for k in range(1, max_half):
        s = str(k)
        t = s[::-1]  # Full reverse of the string for even-length palindrome
        pal_str = s + t
        pal_num = int(pal_str)
        square = pal_num * pal_num
        if square > R:
            break
        if square >= L and is_palindrome(str(square)):
            count += 1
            
    return count

# Example usage:
print(superpalindromesInRange("4", "1000"))  # Expected output: 4
← Back to All Questions