Algorithm
Problem Name: 906. Super Palindromes
Problem Link: https://leetcode.com/problems/super-palindromes/
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 <= 18leftandrightconsist of only digits.leftandrightcannot have leading zeros.leftandrightrepresent integers in the range[1, 1018 - 1].leftis less than or equal toright.
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const superpalindromesInRange = function(left, right) {
const palindromes = []
let res = 0
for(let i = 1; i < 10; i++) {
palindromes.push(`${i}`)
}
for(let i = 1; i < 1e4; i++) {
let l = `${i}`, r = l.split('').reverse().join('')
palindromes.push(`${l}${r}`)
for(let j = 0; j < 10; j++) {
palindromes.push(`${l}${j}${r}`)
}
}
for(let p of palindromes) {
const square = BigInt(p) * BigInt(p)
if(!isPalindrome(`${square}`)) continue
if(BigInt(left) <= square && square < = BigInt(right)) res++
}
return res
function isPalindrome(str) {
let i = 0;
let j = str.length - 1;
while (i < j) {
if (str.charAt(i) !== str.charAt(j)> {
return false;
}
i++;
j--;
}
return true;
}
};
Input
left = "4", right = "1000"
Output
4
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def superpalindromesInRange(self, L, R):
L, R = int(L), int(R)
left = int(math.floor(math.sqrt(L)))
right = int(math.ceil(math.sqrt(R)))
n1, n2 = len(str(left)), len(str(right))
n1 = n1//2 if n1%2==0 else n1//2+1
n2 = n2//2 if n2%2==0 else n2//2+1
start = int('1' + '0'*(n1 - 1))
end = int('9' * n2) + 1
ans = 0
for i in range(start, end):
x = str(i)
num1 = int(x + x[::-1])
num2 = int(x + x[:-1][::-1])
for num in [num1, num2]:
cand = num * num
if L <= cand <= R and str(cand) == str(cand)[::-1]:
ans += 1
return ans
Input
left = "4", right = "1000"
Output
4