Input: left ="4", right ="1000"Output: 4Explanation: 4,9,121, and 484 are superpalindromes.Note that 676is not a superpalindrome:26*26=676, but 26is not a palindrome.
We generate all palindromic numbers up to the square root of right, square them, and check if the result is a palindrome and within the range. Both odd and even length palindromes are considered.
We generate all palindromic numbers up to the square root of right, square them, and check if the result is a palindrome and within the range. We check both odd and even length palindromes.
classSolution {
public:bool isPalindrome(longlong x) {
string s = to_string(x);
int l =0, r = s.size() -1;
while (l < r) if (s[l++] != s[r--]) return false;
return true;
}
intsuperpalindromesInRange(string left, string right) {
longlong l = stoll(left), r = stoll(right), ans =0;
// Odd length palindromes
for (int k =1; k <100000; ++k) {
string s = to_string(k), t = s;
reverse(t.begin(), t.end() -1);
string pal = s + t.substr(1);
longlong v = stoll(pal);
longlong sq = v * v;
if (sq > r) break;
if (sq >= l && isPalindrome(sq)) ++ans;
}
// Even length palindromes
for (int k =1; k <100000; ++k) {
string s = to_string(k), t = s;
reverse(t.begin(), t.end());
string pal = s + t;
longlong v = stoll(pal);
longlong sq = v * v;
if (sq > r) break;
if (sq >= l && isPalindrome(sq)) ++ans;
}
return ans;
}
};
classSolution {
privatebooleanisPalindrome(long x) {
String s = Long.toString(x);
int l = 0, r = s.length() - 1;
while (l < r) if (s.charAt(l++) != s.charAt(r--)) returnfalse;
returntrue;
}
publicintsuperpalindromesInRange(String left, String right) {
long l = Long.parseLong(left), r = Long.parseLong(right), ans = 0;
// Odd length palindromesfor (int k = 1; k < 100000; ++k) {
String s = Integer.toString(k);
StringBuilder t =new StringBuilder(s).reverse();
String pal = s + t.substring(1);
long v = Long.parseLong(pal);
long sq = v * v;
if (sq > r) break;
if (sq >= l && isPalindrome(sq)) ++ans;
}
// Even length palindromesfor (int k = 1; k < 100000; ++k) {
String s = Integer.toString(k);
StringBuilder t =new StringBuilder(s).reverse();
String pal = s + t;
long v = Long.parseLong(pal);
long sq = v * v;
if (sq > r) break;
if (sq >= l && isPalindrome(sq)) ++ans;
}
return (int)ans;
}
}
classSolution {
privatefunisPalindrome(x: Long): Boolean {
val s = x.toString()
return s == s.reversed()
}
funsuperpalindromesInRange(left: String, right: String): Int {
val l = left.toLong()
val r = right.toLong()
var ans = 0for (k in1 until 100000) {
val s = k.toString()
val pal1 = (s + s.dropLast(1).reversed()).toLong()
val sq1 = pal1 * pal1
if (sq1 > r) breakif (sq1 >= l && isPalindrome(sq1)) ans++ }
for (k in1 until 100000) {
val s = k.toString()
val pal2 = (s + s.reversed()).toLong()
val sq2 = pal2 * pal2
if (sq2 > r) breakif (sq2 >= l && isPalindrome(sq2)) ans++ }
return ans
}
}
classSolution:
defsuperpalindromesInRange(self, left: str, right: str) -> int:
l, r = int(left), int(right)
ans =0# Odd length palindromesfor k in range(1, 100000):
s = str(k)
pal = int(s + s[-2::-1])
sq = pal * pal
if sq > r: breakif sq >= l and str(sq) == str(sq)[::-1]:
ans +=1# Even length palindromesfor k in range(1, 100000):
s = str(k)
pal = int(s + s[::-1])
sq = pal * pal
if sq > r: breakif sq >= l and str(sq) == str(sq)[::-1]:
ans +=1return ans
impl Solution {
pubfnsuperpalindromes_in_range(left: String, right: String) -> i32 {
let l = left.parse::<u64>().unwrap();
let r = right.parse::<u64>().unwrap();
letmut ans =0;
for k in1..100_000 {
let s = k.to_string();
let pal1 =format!("{}{}", s, s.chars().rev().skip(1).collect::<String>());
let v1 = pal1.parse::<u64>().unwrap();
let sq1 = v1 * v1;
if sq1 > r { break; }
if sq1 >= l && sq1.to_string() == sq1.to_string().chars().rev().collect::<String>() {
ans +=1;
}
}
for k in1..100_000 {
let s = k.to_string();
let pal2 =format!("{}{}", s, s.chars().rev().collect::<String>());
let v2 = pal2.parse::<u64>().unwrap();
let sq2 = v2 * v2;
if sq2 > r { break; }
if sq2 >= l && sq2.to_string() == sq2.to_string().chars().rev().collect::<String>() {
ans +=1;
}
}
ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
functionsuperpalindromesInRange(left: string, right: string):number {
constl=BigInt(left), r=BigInt(right);
letans=0;
for (letk=1; k<100000; ++k) {
consts=k.toString();
constpal1=BigInt(s+s.slice(0, -1).split('').reverse().join(''));
constsq1=pal1*pal1;
if (sq1>r) break;
if (sq1>=l&&sq1.toString() ===sq1.toString().split('').reverse().join('')) ans++;
}
for (letk=1; k<100000; ++k) {
consts=k.toString();
constpal2=BigInt(s+s.split('').reverse().join(''));
constsq2=pal2*pal2;
if (sq2>r) break;
if (sq2>=l&&sq2.toString() ===sq2.toString().split('').reverse().join('')) ans++;
}
returnans;
}