Description
Let's say a positive integer is a super-palindrome if it is a palindrome, and it is also the square of a palindrome.
Given two positive integers left and right represented as strings, return the number of super-palindromes integers in the inclusive range [left, right].
Example 1:
Input: left = "4", right = "1000"
Output: 4
Explanation: 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
Constraints:
1 <= left.length, right.length <= 18left 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.
Solutions
Solution 1: Preprocessing + Enumeration
According to the problem description, we assume that the super palindrome number x = p2 ∈ [1, 1018), where p is a palindrome number, so p ∈ [1, 109). 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.
Next, we traverse the array ps. For each p, we calculate p2, check whether it is in the interval [L, R], and also check whether p2 is a palindrome number. If it is, the answer is incremented by one.
After the traversal, return the answer.
The time complexity is O(M1⁄4 × log M), and the space complexity is O(M1⁄4). Where M is the upper bound of L and R, and in this problem, M ≤ 1018.
Similar problems:
PythonJavaC++GoTypeScript
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))(code-box)
class Solution {
private static long[] ps;
static {
ps = new long[2 * (int) 1e5];
for (int i = 1; i <= 1e5; i++) {
String s = Integer.toString(i);
String t1 = new StringBuilder(s).reverse().toString();
String t2 = new StringBuilder(s.substring(0, s.length() - 1)).reverse().toString();
ps[2 * i - 2] = Long.parseLong(s + t1);
ps[2 * i - 1] = Long.parseLong(s + t2);
}
}
public int superpalindromesInRange(String left, String right) {
long l = Long.parseLong(left);
long r = Long.parseLong(right);
int ans = 0;
for (long p : ps) {
long x = p * p;
if (x >= l && x <= r && isPalindrome(x)) {
++ans;
}
}
return ans;
}
private boolean isPalindrome(long x) {
long y = 0;
for (long t = x; t > 0; t /= 10) {
y = y * 10 + t % 10;
}
return x == y;
}
}(code-box)
using ll = unsigned long long;
ll ps[2 * 100000];
int init = [] {
for (int i = 1; i <= 100000; i++) {
string s = to_string(i);
string t1 = s;
reverse(t1.begin(), t1.end());
string t2 = s.substr(0, s.length() - 1);
reverse(t2.begin(), t2.end());
ps[2 * i - 2] = stoll(s + t1);
ps[2 * i - 1] = stoll(s + t2);
}
return 0;
}();
class Solution {
public:
int superpalindromesInRange(string left, string right) {
ll l = stoll(left), r = stoll(right);
int ans = 0;
for (ll p : ps) {
ll x = p * p;
if (x >= l && x <= r && is_palindrome(x)) {
++ans;
}
}
return ans;
}
bool is_palindrome(ll x) {
ll y = 0;
for (ll t = x; t; t /= 10) {
y = y * 10 + t % 10;
}
return x == y;
}
};(code-box)
var ps [2 * 100000]int64
func init() {
for i := 1; i <= 100000; i++ {
s := strconv.Itoa(i)
t1 := reverseString(s)
t2 := reverseString(s[:len(s)-1])
ps[2*i-2], _ = strconv.ParseInt(s+t1, 10, 64)
ps[2*i-1], _ = strconv.ParseInt(s+t2, 10, 64)
}
}
func reverseString(s string) string {
cs := []rune(s)
for i, j := 0, len(cs)-1; i < j; i, j = i+1, j-1 {
cs[i], cs[j] = cs[j], cs[i]
}
return string(cs)
}
func superpalindromesInRange(left string, right string) (ans int) {
l, _ := strconv.ParseInt(left, 10, 64)
r, _ := strconv.ParseInt(right, 10, 64)
isPalindrome := func(x int64) bool {
var y int64
for t := x; t > 0; t /= 10 {
y = y*10 + int64(t%10)
}
return x == y
}
for _, p := range ps {
x := p * p
if x >= l && x <= r && isPalindrome(x) {
ans++
}
}
return
}(code-box)
const ps = Array(2e5).fill(0);
const init = (() => {
for (let i = 1; i <= 1e5; ++i) {
const s: string = i.toString();
const t1: string = s.split('').reverse().join('');
const t2: string = s.slice(0, -1).split('').reverse().join('');
ps[2 * i - 2] = parseInt(s + t1, 10);
ps[2 * i - 1] = parseInt(s + t2, 10);
}
})();
function superpalindromesInRange(left: string, right: string): number {
const l = BigInt(left);
const r = BigInt(right);
const isPalindrome = (x: bigint): boolean => {
const s: string = x.toString();
return s === s.split('').reverse().join('');
};
let ans = 0;
for (const p of ps) {
const x = BigInt(p) * BigInt(p);
if (x >= l && x <= r && isPalindrome(x)) {
++ans;
}
}
return ans;
}(code-box)
