LeetCode 906: Super Palindromes

Problem Restatement

A positive integer is called a super-palindrome if:

1. The number itself is a palindrome.
2. It is the square of another palindrome.

We are given two positive integers left and right as strings.

Return how many super-palindromes are in the inclusive range:

[left, right]

For example, 9 is a super-palindrome because:

9 = 3 * 3

and both 9 and 3 are palindromes.

The official problem uses string inputs because the range can go up to around 10^18. The definition and examples match the LeetCode statement.

Input and Output

Function shape:

def superpalindromesInRange(left: str, right: str) -> int:
    ...

Examples

Example 1:

left = "4"
right = "1000"

The super-palindromes are:

4, 9, 121, 484

They come from palindromic roots:

2 * 2 = 4
3 * 3 = 9
11 * 11 = 121
22 * 22 = 484

Answer:

4

676 is a palindrome, but it is not counted because:

676 = 26 * 26

and 26 is not a palindrome.

Example 2:

left = "1"
right = "2"

The only valid number is:

1

Answer:

1

First Thought: Check Every Number

A direct approach is to loop through every number from left to right.

For each number x:

1. Check whether x is a palindrome.
2. Check whether x has an integer square root.
3. Check whether that square root is also a palindrome.

This is far too slow because right can be as large as 10^18 - 1 under the constraints listed by common references for the problem.

We need to search through possible roots instead.

Key Insight

If x is a super-palindrome, then:

x = p * p

where p is a palindrome.

So instead of checking every possible x, we generate palindromic roots p, square them, and check whether the square is also a palindrome.

Since:

x <= 10^18 - 1

we only need:

p <= sqrt(10^18 - 1)

That is less than:

10^9

But we still should not loop over all numbers up to 10^9.

Instead, we generate only palindromic roots.

A palindrome root can be generated from its first half.

For example, from "123":

Odd length palindrome:

"123" + "21" = "12321"

Even length palindrome:

"123" + "321" = "123321"

This gives all palindromic roots without testing every integer.

Algorithm

Convert bounds to integers:

L = int(left)
R = int(right)

Then enumerate possible first halves.

For each integer half:

1. Convert half to string.
2. Build an odd-length palindrome root.
3. Square it.
4. If the square is in range and is a palindrome, count it.
5. Build an even-length palindrome root.
6. Square it.
7. If the square is in range and is a palindrome, count it.

We can stop once the smallest generated square is larger than R, but using a safe fixed bound also works.

Since roots are below 10^9, their first half has at most 5 digits. So enumerating half from 1 to 100000 is enough.

Palindrome Check

We can check palindromes by converting the number to a string:

def is_palindrome(x: int) -> bool:
    s = str(x)
    return s == s[::-1]

This is simple and fast enough here.

Correctness

Every number counted by the algorithm is valid.

The algorithm only counts a square square = root * root when:

1. root was generated as a palindrome.
2. square lies in [L, R].
3. square is also a palindrome.

Therefore, every counted number is a super-palindrome in the required range.

Now we show that every valid super-palindrome is counted.

Let x be any super-palindrome in [L, R].

By definition, there exists a palindromic integer p such that:

x = p * p

Since x <= R <= 10^18 - 1, we have p < 10^9.

Every positive palindrome less than 10^9 can be formed by taking its first half and mirroring it, either as an odd-length or even-length palindrome.

The algorithm enumerates all such first halves and constructs both odd and even palindromic roots.

So it eventually constructs p, computes p * p, checks that it lies in range, and counts it.

Thus no valid super-palindrome is missed.

Complexity

Here d is the number of digits, at most 18 for the squared value.

Implementation

class Solution:
    def superpalindromesInRange(self, left: str, right: str) -> int:
        L = int(left)
        R = int(right)

        def is_palindrome(x: int) -> bool:
            s = str(x)
            return s == s[::-1]

        answer = 0

        for half in range(1, 100000):
            s = str(half)

            odd_root = int(s + s[-2::-1])
            odd_square = odd_root * odd_root

            if odd_square > R:
                break

            if odd_square >= L and is_palindrome(odd_square):
                answer += 1

            even_root = int(s + s[::-1])
            even_square = even_root * even_root

            if even_square >= L and even_square <= R and is_palindrome(even_square):
                answer += 1

        return answer

Code Explanation

The bounds arrive as strings, so we convert them first:

L = int(left)
R = int(right)

The helper checks whether a number reads the same backward and forward:

def is_palindrome(x: int) -> bool:
    s = str(x)
    return s == s[::-1]

We enumerate possible left halves:

for half in range(1, 100000):

For odd-length roots, we do not duplicate the middle digit:

odd_root = int(s + s[-2::-1])

For example:

s = "123"
odd_root = 12321

Then we square the root:

odd_square = odd_root * odd_root

If the odd square already exceeds the right bound, later odd roots will only be larger, so we can stop:

if odd_square > R:
    break

Then we count it if it is inside the range and palindromic:

if odd_square >= L and is_palindrome(odd_square):
    answer += 1

For even-length roots, we mirror the whole half:

even_root = int(s + s[::-1])

For example:

s = "123"
even_root = 123321

Then we check its square in the same way:

if even_square >= L and even_square <= R and is_palindrome(even_square):
    answer += 1

Testing

def run_tests():
    s = Solution()

    assert s.superpalindromesInRange("4", "1000") == 4
    assert s.superpalindromesInRange("1", "2") == 1
    assert s.superpalindromesInRange("1", "1") == 1
    assert s.superpalindromesInRange("2", "3") == 0
    assert s.superpalindromesInRange("9", "9") == 1
    assert s.superpalindromesInRange("121", "121") == 1
    assert s.superpalindromesInRange("122", "483") == 0
    assert s.superpalindromesInRange("484", "484") == 1

    print("all tests passed")

run_tests()

Test meaning: