In this guide, you will get 906. Super Palindromes LeetCode Solution with the best time and space complexity. The solution to Super Palindromes problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 <= 18
left 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.
Complexity Analysis
Time Complexity:
Space Complexity:
906. Super Palindromes LeetCode Solution in C++
class Solution {
public:
int superpalindromesInRange(string left, string right) {
int ans = 0;
const long l = stoll(left);
const long r = stoll(right);
for (long i = sqrt(l); i * i <= r;) {
const long palindrome = nextPalindrome(i);
const long squared = palindrome * palindrome;
if (squared <= r && isPalindrome(squared))
++ans;
i = palindrome + 1;
}
return ans;
}
private:
long nextPalindrome(int num) {
const string s = to_string(num);
const int n = s.length();
string half = s.substr(0, (n + 1) / 2);
string reversedHalf = reversed(half.substr(0, n / 2));
const long candidate = stoll(half + reversedHalf);
if (candidate >= num)
return candidate;
half = to_string(stoll(half) + 1);
reversedHalf = reversed(half.substr(0, n / 2));
return stoll(half + reversedHalf);
}
string reversed(const string& s) {
return {s.rbegin(), s.rend()};
}
bool isPalindrome(long num) {
const string s = to_string(num);
int l = 0;
int r = s.length() - 1;
while (l < r)
if (s[l++] != s[r--])
return false;
return true;
}
}; /* code provided by PROGIEZ */
906. Super Palindromes LeetCode Solution in Java
class Solution {
public int superpalindromesInRange(String left, String right) {
int ans = 0;
Long l = Long.valueOf(left);
Long r = Long.valueOf(right);
for (long i = (long) Math.sqrt(l); i * i <= r;) {
long palindrome = nextPalindrome(i);
long squared = palindrome * palindrome;
if (squared <= r && isPalindrome(squared))
++ans;
i = palindrome + 1;
}
return ans;
}
private long nextPalindrome(long num) {
final String s = String.valueOf(num);
final int n = s.length();
String half = s.substring(0, (n + 1) / 2);
String reversedHalf = new StringBuilder(half.substring(0, n / 2)).reverse().toString();
final long candidate = Long.valueOf(half + reversedHalf);
if (candidate >= num)
return candidate;
half = String.valueOf(Long.valueOf(half) + 1);
reversedHalf = new StringBuilder(half.substring(0, n / 2)).reverse().toString();
return Long.valueOf(half + reversedHalf);
}
private boolean isPalindrome(long num) {
final String s = String.valueOf(num);
int l = 0;
int r = s.length() - 1;
while (l < r)
if (s.charAt(l++) != s.charAt(r--))
return false;
return true;
}
} // code provided by PROGIEZ
906. Super Palindromes LeetCode Solution in Python
class Solution:
def superpalindromesInRange(self, left: str, right: str) -> int:
def nextPalindrome(num: int) -> int:
s = str(num)
n = len(s)
half = s[0:(n + 1) // 2]
reversedHalf = half[:n // 2][::-1]
candidate = int(half + reversedHalf)
if candidate >= num:
return candidate
half = str(int(half) + 1)
reversedHalf = half[:n // 2][::-1]
return int(half + reversedHalf)
def isPalindrome(num: int) -> bool:
s = str(num)
l = 0
r = len(s) - 1
while l < r:
if s[l] != s[r]:
return False
l += 1
r -= 1
return True
ans = 0
l = int(left)
r = int(right)
i = math.isqrt(l)
while i * i <= r:
palindrome = nextPalindrome(i)
squared = palindrome**2
if squared <= r and isPalindrome(squared):
ans += 1
i = palindrome + 1
return ans # code by PROGIEZ
