##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/906.html

# 906. Super Palindromes (Hard)

Let's say a positive integer is a superpalindrome if it is a palindrome, and it is also the square of a palindrome.

Now, given two positive integers L and R (represented as strings), return the number of superpalindromes in the inclusive range [L, R].

Example 1:

Input: L = "4", R = "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.

Note:

1. 1 <= len(L) <= 18
2. 1 <= len(R) <= 18
3. L and R are strings representing integers in the range [1, 10^18).
4. int(L) <= int(R)

Companies:

Related Topics:
Math

## Solution 1.

• class Solution {
public int superpalindromesInRange(String L, String R) {
long squareLow = Long.parseLong(L), squareHigh = Long.parseLong(R);
long low = (long) Math.ceil(Math.sqrt(squareLow));
long high = (long) Math.floor(Math.sqrt(squareHigh));
int count = 0;
for (int i = 1; i < 100000; i++) {
long palindrome = getOddLengthPalindrome(i);
if (palindrome < low)
continue;
else if (palindrome > high)
break;
else {
long square = palindrome * palindrome;
if (isPalindrome(square))
count++;
}
}
for (int i = 1; i < 100000; i++) {
long palindrome = getEvenLengthPalindrome(i);
if (palindrome < low)
continue;
else if (palindrome > high)
break;
else {
long square = palindrome * palindrome;
if (isPalindrome(square))
count++;
}
}
return count;
}

public long getOddLengthPalindrome(int num) {
StringBuffer sb = new StringBuffer(String.valueOf(num));
int length = sb.length();
for (int i = length - 2; i >= 0; i--)
sb.append(sb.charAt(i));
return Long.parseLong(sb.toString());
}

public long getEvenLengthPalindrome(int num) {
StringBuffer sb = new StringBuffer(String.valueOf(num));
int length = sb.length();
for (int i = length - 1; i >= 0; i--)
sb.append(sb.charAt(i));
return Long.parseLong(sb.toString());
}

public boolean isPalindrome(long num) {
char[] array = String.valueOf(num).toCharArray();
int left = 0, right = array.length - 1;
while (left < right) {
if (array[left] != array[right])
return false;
left++;
right--;
}
return true;
}
}

• // OJ: https://leetcode.com/problems/super-palindromes/
// Time: O(W^(1/4)*logW)
// Space: O(logW)
class Solution {
long getPalindrome(long half, bool odd) {
long ans = half;
if (odd) half /= 10;
for (; half; half /= 10) ans = ans * 10 + half % 10;
return ans;
}
bool isPalindrome(long n) {
long tmp = n, r = 0;
for (; tmp; tmp /= 10) r = r * 10 + tmp % 10;
return r == n;
}
public:
int superpalindromesInRange(string left, string right) {
long L = stoll(left), R = stoll(right), ans = 0;
for (int len = 1; true; ++len) {
for (long half = pow(10L, (len - 1) / 2), end = half * 10; half < end; ++half) {
long pal = getPalindrome(half, len % 2), sq = pal * pal;
if (sq < L) continue;
if (sq > R) return ans;
ans += isPalindrome(sq);
}
}
return 0;
}
};

• class Solution:
def superpalindromesInRange(self, L, R):
"""
:type L: str
:type R: str
:rtype: int
"""
que = collections.deque(["11", "22"])
candi = set()
while que:
size = len(que)
for _ in range(size):
p = que.popleft()
if int(p) ** 2 > int(R):
continue
for j in ["0", "1", "2"]:
q = (p[:len(p)//2] + j + p[len(p)//2:])
que.append(q)
res = 0
for cand in candi:
if int(L) <= int(cand) ** 2 <= int(R) and self.isPalindromes(int(cand) ** 2):
res += 1
return res

def isPalindromes(self, s):
s = str(s)
N = len(s)
for l in range(1, N // 2):
if s[l] != s[N - 1 - l]:
return False
return True

• 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
}

• 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;
}