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.

#906

Hard

auto_awesome数学·string

LeetCode 题解工作台

超级回文数

如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。现在，给你两个以字符串形式表示的正整数 left 和 right ，统计并返回区间 [left, right] 中的超级回文数的数目。示例 1：输入： left = "4", right = "100…

数学字符串枚举

题目描述

如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为 超级回文数 。

现在，给你两个以字符串形式表示的正整数 left 和 right ，统计并返回区间 [left, right] 中的 超级回文数 的数目。

示例 1：

输入：left = "4", right = "1000"
输出：4
解释：4、9、121 和 484 都是超级回文数。
注意 676 不是超级回文数：26 * 26 = 676 ，但是 26 不是回文数。

示例 2：

输入：left = "1", right = "2"
输出：1

提示：

1 <= left.length, right.length <= 18
left 和 right 仅由数字（0 - 9）组成。
left 和 right 不含前导零。
left 和 right 表示的整数在区间 [1, 10¹⁸ - 1] 内。
left 小于等于 right 。

lightbulb

解题思路

方法一：预处理 + 枚举

根据题目描述，我们假设超级回文数 $x = p^2 \in [1, 10^{18})$ ，其中 $p$ 是回文数，那么 $p \in [1, 10^9)$ 。我们可以枚举回文数 $p$ 的前半部分，然后将其翻转后拼接，得到所有的回文数，记录在数组 $ps$ 中。

接下来，我们遍历数组 $ps$ ，对于每个 $p$ ，我们计算 $p^2$ ，判断是否在区间 $[L, R]$ 中，同时判断 $p^2$ 是否是回文数，若是，答案加一。

遍历结束后，返回答案即可。

时间复杂度 $O(M^{\frac{1}{4}} \times \log M)$ ，空间复杂度 $O(M^{\frac{1}{4}})$ 。其中 $M$ 是 $L$ 和 $R$ 的上界，本题中 $M \leq 10^{18}$ 。

相似题目：

2967. 使数组成为等数数组的最小代价

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

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))

speed

复杂度分析

指标	值
时间	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.
空间	O(\log W)

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#902 最大为 N 的数字组合 #899 有序队列 #869 重新排序得到 2 的幂