LeetCode Problem 906

Difficulty: 🔴 Hard
Topics: Math, String, Enumeration

Solution

LeetCode 906 - Super Palindromes

Problem Understanding

This problem asks us to count how many numbers within a given inclusive range are "super-palindromes".

A number is considered a super-palindrome if both of the following conditions are true:

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

For example:

• 121 is a palindrome.
• 121 = 11 * 11
• 11 is also a palindrome.

Therefore, 121 is a super-palindrome.

The input consists of two strings, left and right, which represent the lower and upper bounds of the search range. These values can be extremely large, up to 10^18 - 1, which means we cannot rely on simple brute-force iteration across the entire interval.

The goal is to return the total number of integers x such that:

• left <= x <= right
• x is a palindrome
• sqrt(x) is also a palindrome integer

The constraints are very important here:

• The range endpoints can contain up to 18 digits.
• The interval can therefore span nearly one quintillion numbers.
• Any approach that checks every number in the range is completely infeasible.

The key observation is that super-palindromes are very rare. Instead of searching every number in the range, we should generate palindrome roots directly, square them, and then test whether the square is also a palindrome.

Several edge cases are important:

• Very small ranges like [1, 2]
• Ranges containing only one number
• Large ranges near 10^18
• Palindromic squares whose roots are not palindromes, such as 676 = 26^2
• Numbers whose square roots exceed integer limits if handled carelessly

The problem guarantees:

• Inputs are valid positive integers
• No leading zeros exist
• left <= right

This allows us to focus entirely on efficient generation and validation.

Approaches

Brute Force Approach

A straightforward solution would iterate through every number in the interval [left, right].

For each number:

1. Check whether the number itself is a palindrome.
2. Compute its integer square root.
3. Verify that the square root squared equals the number.
4. Check whether the square root is also a palindrome.

This approach is logically correct because it directly verifies the definition of a super-palindrome.

However, the constraints make this impossible in practice. The range may contain up to 10^18 numbers, which is far beyond computational feasibility.

Even if palindrome checking is efficient, iterating through such a massive interval cannot finish within time limits.

Optimal Approach

The crucial insight is that super-palindromes are generated from palindromic roots.

Instead of iterating through all numbers in the range, we generate all palindrome numbers whose squares could possibly fall inside the range.

Suppose:

x = y^2

If x <= 10^18, then:

y <= 10^9

This drastically reduces the search space.

Now observe something even more important:

• We only care about palindrome roots.
• The number of palindrome integers below 10^9 is actually quite small.

We can efficiently construct palindromes by mirroring digits:

• Odd-length palindromes
• Even-length palindromes

For each generated palindrome root:

1. Square it.
2. Stop if the square exceeds right.
3. Check whether the square itself is a palindrome.
4. Count it if it lies within the range.

This transforms the problem from searching billions or quintillions of values into generating only tens of thousands of palindrome candidates.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(right - left)	O(1)	Checks every number individually
Optimal	O(P log P)	O(1)	Generates only palindrome roots

Here, P represents the number of generated palindrome roots, which is very small compared to the interval size.

Algorithm Walkthrough

1. Convert left and right from strings into integers so numerical comparisons become efficient.
2. Compute the upper bound for possible roots. Since right <= 10^18, any valid root must satisfy:

root^2 <= right

Therefore:

root <= sqrt(right)

3. Generate palindrome roots instead of checking every number.

We generate two types:

• Odd-length palindromes
• Even-length palindromes

This ensures we cover all palindrome integers. 4. To build an odd-length palindrome:

• Start with a base number like "123"
• Mirror all digits except the last one
• Result becomes "12321"

5. To build an even-length palindrome:

• Start with "123"
• Mirror the entire string
• Result becomes "123321"

6. Convert each generated palindrome root into an integer.
7. Square the palindrome root.
8. If the square exceeds right, stop processing larger palindromes of that type because generated palindromes grow monotonically.
9. Check whether the square itself is a palindrome.
10. If:

• left <= square <= right
• and the square is palindromic

increment the answer. 11. Continue until all possible palindrome roots are processed.

Why it works

Every super-palindrome must be the square of a palindromic integer. Therefore, instead of searching all numbers in the target range, it is sufficient to enumerate all palindrome roots whose squares could fall inside the interval.

The algorithm generates every possible palindrome root exactly once. For each root, it checks whether the square is also palindromic. Since every valid super-palindrome originates from such a root, the algorithm counts all valid answers without missing any cases.

Python Solution

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

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

        count = 0

        # Generate odd-length palindrome roots
        k = 1
        while True:
            s = str(k)
            palindrome = int(s + s[-2::-1])

            square = palindrome * palindrome

            if square > right_num:
                break

            if square >= left_num and is_palindrome(square):
                count += 1

            k += 1

        # Generate even-length palindrome roots
        k = 1
        while True:
            s = str(k)
            palindrome = int(s + s[::-1])

            square = palindrome * palindrome

            if square > right_num:
                break

            if square >= left_num and is_palindrome(square):
                count += 1

            k += 1

        return count

The implementation begins by converting the string bounds into integers for efficient arithmetic operations.

The helper function is_palindrome converts a number into a string and compares it with its reverse. This is an efficient and readable way to perform palindrome checks.

The solution then separately generates odd-length and even-length palindrome roots.

For odd-length palindromes:

s + s[-2::-1]

mirrors every digit except the last one.

Example:

"123" -> "12321"

For even-length palindromes:

s + s[::-1]

mirrors the entire string.

Example:

"123" -> "123321"

Each palindrome root is squared immediately. If the square exceeds the upper bound, the loop terminates because future palindromes will only become larger.

Whenever a square lies within the target interval and is itself palindromic, the answer counter increases.

The algorithm avoids unnecessary work because it only explores mathematically relevant candidates.

Go Solution

package main

import (
	"strconv"
)

func superpalindromesInRange(left string, right string) int {
	leftNum, _ := strconv.ParseInt(left, 10, 64)
	rightNum, _ := strconv.ParseInt(right, 10, 64)

	isPalindrome := func(value int64) bool {
		s := strconv.FormatInt(value, 10)

		i := 0
		j := len(s) - 1

		for i < j {
			if s[i] != s[j] {
				return false
			}

			i++
			j--
		}

		return true
	}

	count := 0

	// Odd-length palindrome roots
	for k := 1; ; k++ {
		s := strconv.Itoa(k)

		palStr := s
		for i := len(s) - 2; i >= 0; i-- {
			palStr += string(s[i])
		}

		palindrome, _ := strconv.ParseInt(palStr, 10, 64)

		square := palindrome * palindrome

		if square > rightNum {
			break
		}

		if square >= leftNum && isPalindrome(square) {
			count++
		}
	}

	// Even-length palindrome roots
	for k := 1; ; k++ {
		s := strconv.Itoa(k)

		palStr := s
		for i := len(s) - 1; i >= 0; i-- {
			palStr += string(s[i])
		}

		palindrome, _ := strconv.ParseInt(palStr, 10, 64)

		square := palindrome * palindrome

		if square > rightNum {
			break
		}

		if square >= leftNum && isPalindrome(square) {
			count++
		}
	}

	return count
}

The Go implementation follows the same logic as the Python version but uses explicit string construction because Go does not provide Python-style slicing syntax.

strconv.ParseInt converts strings into integers, while strconv.FormatInt converts integers back into strings for palindrome checking.

The palindrome validation uses a two-pointer technique instead of reversing the string. This avoids allocating a second reversed string and is idiomatic in Go.

All arithmetic uses int64 because values may approach 10^18.

Worked Examples

Example 1

Input

left = "4"
right = "1000"

Step-by-step execution

Generated Root	Root Palindrome	Square	Square Palindrome?	In Range?	Count
1	Yes	1	Yes	No	0
2	Yes	4	Yes	Yes	1
3	Yes	9	Yes	Yes	2
4	Yes	16	No	Yes	2
11	Yes	121	Yes	Yes	3
22	Yes	484	Yes	Yes	4
26	No root generation	676	Yes	Ignored	4

Final answer:

4

The valid super-palindromes are:

4, 9, 121, 484

Example 2

Input

left = "1"
right = "2"

Step-by-step execution

Generated Root	Square	Square Palindrome?	In Range?	Count
1	1	Yes	Yes	1
2	4	Yes	No	1

Final answer:

1

Only 1 qualifies.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(P log P)	P palindrome roots are generated, palindrome checks cost logarithmic time
Space	O(1)	Only a few variables are used

The number of generated palindrome roots is relatively small because roots only need to go up to 10^9, and only palindrome roots are considered.

Palindrome construction and palindrome checking both operate on digit strings whose length is at most 18, so each operation is effectively constant time in practice.

The algorithm is therefore extremely efficient for the problem constraints.

Test Cases

sol = Solution()

assert sol.superpalindromesInRange("4", "1000") == 4  # Provided example
assert sol.superpalindromesInRange("1", "2") == 1  # Smallest valid range
assert sol.superpalindromesInRange("1", "1") == 1  # Single-number range with valid answer
assert sol.superpalindromesInRange("2", "3") == 0  # No super-palindromes
assert sol.superpalindromesInRange("9", "9") == 1  # Single palindrome square
assert sol.superpalindromesInRange("10", "120") == 0  # No valid values in range
assert sol.superpalindromesInRange("121", "121") == 1  # Exact super-palindrome
assert sol.superpalindromesInRange("484", "484") == 1  # Another exact match
assert sol.superpalindromesInRange("676", "676") == 0  # Palindrome but root is not palindrome
assert sol.superpalindromesInRange("1", "100000") == 10  # Larger interval
assert sol.superpalindromesInRange("40000000000000000", "50000000000000000") >= 0  # Large values

Test Summary

Test	Why
"4", "1000"	Verifies provided example
"1", "2"	Tests smallest range
"1", "1"	Single valid value
"2", "3"	No valid answers
"9", "9"	Single-number valid palindrome
"10", "120"	Range excluding valid squares
"121", "121"	Exact boundary match
"484", "484"	Another exact match
"676", "676"	Palindrome square with non-palindrome root
"1", "100000"	Multiple valid values
Very large range	Stress test near upper constraints

Edge Cases

Single-number ranges

A range like:

left = "121"
right = "121"

can easily expose off-by-one errors. Some implementations accidentally treat the interval as exclusive on one side. The solution correctly uses inclusive comparisons:

square >= left_num and square <= right_num

which ensures exact-boundary matches are counted.

Palindromic squares with non-palindromic roots

A number like:

676 = 26^2

is itself a palindrome, but 26 is not. A naive solution that only checks whether the number and its square root relationship exist might incorrectly count it.

This implementation avoids the issue entirely by generating only palindrome roots in the first place.

Extremely large upper bounds

The upper limit may approach:

10^18 - 1

A brute-force solution would fail immediately due to time constraints. Additionally, careless implementations may overflow standard integer types.

The algorithm safely handles this by:

• Generating only relevant palindrome roots
• Using 64-bit integer arithmetic
• Stopping generation as soon as squares exceed the upper bound

This guarantees both correctness and efficiency for the largest allowed inputs.