#906

Hard

LeetCode Problem Workspace

Super Palindromes

Count all super-palindromes in a given numeric range, where each is a palindrome and square of a palindrome.

Problem Statement

A super-palindrome is a positive integer that is itself a palindrome and also the square of a palindrome. For example, 121 is a super-palindrome because 11 squared equals 121, and both 11 and 121 read the same forwards and backwards.

Given two strings left and right representing positive integers, return the count of super-palindromes within the inclusive range [left, right]. Constraints include string lengths up to 18 digits, no leading zeros, and left not exceeding right. Example: left = "4", right = "1000" should return 4.

Examples

Example 1

Input: left = "4", right = "1000"

Output: 4

4, 9, 121, and 484 are superpalindromes. Note that 676 is not a superpalindrome: 26 * 26 = 676, but 26 is not a palindrome.

Example 2

Input: left = "1", right = "2"

Output: 1

Example details omitted.

Constraints

1 <= left.length, right.length <= 18
left and right consist of only digits.
left and right cannot have leading zeros.
left and right represent integers in the range [1, 1018 - 1].
left is less than or equal to right.

Solution Approach

Generate Palindromic Roots

Iterate through potential palindrome roots up to the fourth root of the upper limit. Construct both odd and even length palindromes as strings to prevent numeric overflow, then square them to see if they fall within the range.

Check Squared Palindromes

For each palindromic root, compute the square and convert it to a string. Verify whether this squared number is itself a palindrome. Only count numbers that satisfy both the root and square palindrome condition.

Range Filtering and Optimization

Stop generating roots once their squares exceed the upper bound. Skip any roots whose squares are below the lower bound. Use string comparisons to handle very large numbers safely and efficiently.

Complexity Analysis

Metric	Value
Time	O(W^{\frac{1}{4}} * \log W)
Space	O(\log W)

Time complexity is O(W^{\frac{1}{4}} * \log W) due to iterating palindromic roots up to the fourth root of the upper limit, with logarithmic cost to check each square palindrome. Space complexity is O(\log W) to store temporary string representations of roots and squares.

What Interviewers Usually Probe

Focus on combining string manipulation with math to generate valid palindromic roots.
Check for both odd and even length palindrome squares to avoid missing edge cases.
Handle very large numeric ranges using string-based comparisons to prevent integer overflow.

Common Pitfalls or Variants

Common pitfalls

Assuming all squares of palindrome roots are automatically palindromes.
Overlooking the need to generate both odd and even length palindromes.
Using integer types that cannot accommodate numbers up to 10^{18}.

Follow-up variants

Count super-palindromes within a range but only considering odd-length palindromes.
Return the actual list of super-palindromes instead of just the count.
Modify the problem to find super-palindromes that are cubes of palindromes instead of squares.

FAQ

What is a super-palindrome in this context?

A super-palindrome is a number that is a palindrome itself and also the square of a palindrome number.

Why do we generate palindrome roots as strings?

Using strings prevents integer overflow and allows efficient palindrome construction for both odd and even lengths.

Can GhostInterview handle ranges up to 10^{18}?

Yes, it manages large numeric ranges safely with string-based comparisons and root generation up to the fourth root.

Do we need to check both odd and even length roots?

Yes, some super-palindromes come from odd-length roots while others from even-length roots, missing one type undercounts results.

What pattern does this problem mainly test?

This problem primarily tests the 'Math plus String' pattern, combining numerical calculations with string palindrome checks.

terminal

Solution

Solution 1: Preprocessing + Enumeration

According to the problem description, we assume that the super palindrome number $x = p^2 \in [1, 10^{18})$, where $p$ is a palindrome number, so $p \in [1, 10^9)$. We can enumerate the first half of the palindrome number $p$, then reverse it, and concatenate it to get all palindrome numbers, which are recorded in the array $ps$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

ps = []
for i in range(1, 10**5 + 1):
    s = str(i)
    t1 = s[::-1]
    t2 = s[:-1][::-1]
    ps.append(int(s + t1))
    ps.append(int(s + t2))


class Solution:
    def superpalindromesInRange(self, left: str, right: str) -> int:
        def is_palindrome(x: int) -> bool:
            y, t = 0, x
            while t:
                y = y * 10 + t % 10
                t //= 10
            return x == y

        l, r = int(left), int(right)
        return sum(l <= x <= r and is_palindrome(x) for x in map(lambda x: x * x, ps))

Continue Practicing

#902 numbers at most n given digit set #899 orderly queue #869 reordered power of 2