Super Palindromes: Enumerating Palindromic Squares

LeetCode 906, Super Palindromes, asks you to count super palindromes in a given range. You receive two strings left and right representing the boundaries of a range, and you need to find how many numbers in [left, right] are super palindromes. A number is a super palindrome if it is a palindrome and its square root is also an integer palindrome.

Why this problem matters

Super Palindromes is a beautiful example of how reframing a search problem makes it tractable. The naive approach of checking every number in the range is hopeless when the range can stretch up to 10^18. But once you realize the search space can be dramatically reduced by generating candidates from the "root" side, the problem becomes manageable.

This pattern of generating candidates rather than testing all possibilities shows up frequently in competitive programming and interviews. Problems involving perfect squares, prime factorizations, and digit-based constraints often reward you for flipping the direction of search. Instead of asking "is this number special?", you ask "what numbers could possibly be special?" and enumerate only those.

The math category on LeetCode tends to favor this kind of lateral thinking. You will not grind through this problem with a data structure or a well-known algorithm template. You need to notice the structure of the numbers involved, and that noticing is the entire challenge.

The brute force approach

The most direct approach: iterate through every integer in [left, right], check if it is a palindrome, then check if its square root is an integer and also a palindrome.

The problem? The range can be up to 10^18. Even if you could check a billion numbers per second, you would need a billion seconds to sweep the full range. That is roughly 30 years. The brute force is completely impractical.

You might try to speed things up by only checking perfect squares in the range (since a super palindrome must be a perfect square). You could iterate i from ceil(sqrt(left)) to floor(sqrt(right)) and check if both i and i^2 are palindromes. This narrows the search space to about 10^9 candidates, which is still too slow for a typical time limit.

The key insight

Flip the problem. Instead of searching for super palindromes directly, generate all palindromes up to sqrt(10^18) = 10^9, square each one, and check whether the square is also a palindrome and falls within [left, right].

How many palindromes exist below 10^9? A 9-digit palindrome is determined by its first 5 digits (the rest are mirrored), giving at most 10^5 options per length. Across all lengths from 1 to 9, there are roughly 100,000 palindromes total. Squaring each one and checking if the result is a palindrome takes negligible time. The entire approach runs in well under a second.

Walking through it step by step

The algorithm generates palindromes in two passes: one for odd-length palindromes and one for even-length. For each generated palindrome, it squares the value, checks bounds, and verifies the square is itself a palindrome.

The solution

def superpalindromesInRange(left, right):
    L = int(left)
    R = int(right)
    MAGIC = 100000
    count = 0

    # Odd-length palindromes: k -> k + reverse(k[:-1])
    for k in range(1, MAGIC):
        s = str(k)
        t = s + s[-2::-1]  # e.g., "123" -> "12321"
        v = int(t) ** 2
        if v > R:
            break
        if v >= L and str(v) == str(v)[::-1]:
            count += 1

    # Even-length palindromes: k -> k + reverse(k)
    for k in range(1, MAGIC):
        s = str(k)
        t = s + s[::-1]  # e.g., "12" -> "1221"
        v = int(t) ** 2
        if v > R:
            break
        if v >= L and str(v) == str(v)[::-1]:
            count += 1

    return count

The code has two loops, one for each type of palindrome construction.

Odd-length palindromes: Take a number k, convert it to a string, and mirror everything except the last character. For example, k = 123 produces the string "123" which becomes "12321". The middle digit appears only once.

Even-length palindromes: Take a number k, convert it to a string, and append the full reverse. For example, k = 12 produces "1221". Every digit appears in a mirrored pair.

Together, these two loops enumerate every palindrome from 1 up to approximately 10^9. For each generated palindrome t, we square it and check two conditions: the square must be within [L, R], and the square itself must read the same forwards and backwards.

The MAGIC = 100000 bound ensures we generate palindromes with up to 9 digits (since a 5-digit k produces a 9-digit odd-length palindrome), which when squared can reach up to 10^18.

Complexity analysis

The W^(1/4) factor comes from the number of palindromes up to sqrt(W). Since palindromes up to N number roughly O(N^(1/2)) (determined by half their digits), and we enumerate palindromes up to sqrt(W), the count is approximately O(W^(1/4)). The log W factor accounts for the string operations (reversing and comparing strings of length proportional to log W).

In practice, with W = 10^18, you process about 100,000 candidates, each requiring O(18) character operations. This is fast enough to run in milliseconds.

Building blocks

1. Palindrome generation

The core technique is constructing palindromes from their "first half." Rather than testing every number for the palindrome property, you build numbers that are guaranteed to be palindromes by mirroring digits. This eliminates the need for a palindrome check on the root entirely.

For odd-length: take the first half including the center digit, then mirror the prefix. "abc" -> "abcba".

For even-length: take the first half, then mirror the entire thing. "ab" -> "abba".

2. Palindrome checking

For the squared result, you still need to verify it is a palindrome. The simplest check converts the number to a string and compares it with its reverse. Since these strings are at most 18 characters long, this comparison is essentially free.

Edge cases

• Single-digit super palindromes: The numbers 1, 4, and 9 are all super palindromes (their roots 1, 2, 3 are palindromes, and they themselves are palindromes). Make sure your generation starts from k = 1.
• Left equals right: When the range contains a single number, verify that specific number. Your algorithm handles this naturally since it checks bounds after squaring.
• Large boundaries at the limits: The problem guarantees left and right can be up to 10^18. Using Python avoids integer overflow concerns, but in languages like C++ or Java you would need 64-bit integers (long long / long).
• The number 1: Both 1 and its square root 1 are palindromes. It is a valid super palindrome and should be counted when it falls within the range.
• Even-length palindromic roots that produce non-palindromic squares: For example, 33^2 = 1089 is not a palindrome. Your algorithm correctly skips these.

Common mistakes

1. Forgetting even-length palindromes. Many solutions only generate odd-length palindromes and miss numbers like 484 (whose root 22 is an even-length palindrome).

2. Setting MAGIC too low. If your upper bound for k is too small, you will miss palindromic roots that produce squares within the given range. Since the range can go up to 10^18 and sqrt(10^18) = 10^9, your roots can be up to 9 digits. A 9-digit odd palindrome is generated from a 5-digit k, so MAGIC = 100000 covers all cases.

3. Integer overflow in typed languages. Squaring a number up to 10^9 gives a result up to 10^18. In C++ you need long long, and in Java you need long. Python handles big integers natively.

4. Not breaking early. Since palindromes are generated in increasing order, once the square exceeds R, you can break out of the loop. Forgetting this does not affect correctness but may hurt performance.

5. Checking if the root is a palindrome. You do not need to check this because you constructed it to be a palindrome. The only check needed is on the squared result.

From understanding to recall

The algorithm for Super Palindromes is short and elegant: two small loops, each generating palindromes from their first half, squaring, and checking. When you read through it, the logic is clear. But reproducing it under time pressure is a different matter.

The tricky part is remembering the two palindrome generation formulas. The odd-length version uses s + s[-2::-1] (dropping the last character before reversing), while the even-length version uses s + s[::-1] (reversing the whole thing). Mix these up and you either generate duplicates or miss candidates entirely.

Spaced repetition helps you internalize these small but critical details. After a few review sessions, the distinction between odd and even palindrome construction becomes automatic. You stop thinking about whether to use [-2::-1] or [::-1] because your hands remember the pattern. The conceptual insight (enumerate roots, square, check) is easy to recall. It is the implementation details that need drilling.

Related posts

• Palindrome Number - Check if an integer is a palindrome without string conversion
• Palindromic Substrings - Count palindromic substrings using expand-around-center
• Count Primes - Another enumeration problem where you generate candidates instead of testing all numbers

Super Palindromes teaches you that the best way to find rare objects is to construct them rather than hunt for them. When the search space is astronomical but the answer set is tiny, flip your perspective. Generate the things that could possibly work and verify them. This principle carries far beyond palindromes into primality testing, constraint satisfaction, and any domain where candidates are sparse in a vast space.