Super Palindromes
HardPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most straightforward but highly inefficient approach. The idea is to iterate through every integer x in the given range [left, right]. For each integer, we perform a series of checks to determine if it's a super-palindrome.
Algorithm
- Parse
leftandrightstrings tolongintegersLandR. - Initialize a counter
countto 0. - Iterate through each integer
xfromLtoR. - For each
x, check if it's a super-palindrome:- Calculate
p = sqrt(x). - If
p * p == xandisPalindrome(x)andisPalindrome(p), incrementcount.
- Calculate
- Return
count.
Walkthrough
First, we convert the input strings left and right to long integers, let's call them L and R. We then loop through each number x from L to R. Inside the loop, for each x, we check if it's a super-palindrome:
- Check if
xis a perfect square. We calculate the integer square root ofx, let's sayp = (long)sqrt(x). Ifp * pis not equal tox, thenxis not a perfect square, and we move to the next number. - Check if
xis a palindrome. We convertxto a string and check if the string reads the same forwards and backward. - Check if the root
pis a palindrome. If the first two conditions are met, we then check if the square rootpis also a palindrome. If all three conditions are satisfied, we increment a counter. After checking all numbers in the range, the value of the counter is our answer. A helper functionisPalindrome(long n)would be useful, which converts the number to a string and checks for the palindrome property.
class Solution { public int superpalindromesInRange(String left, String right) { long L = Long.parseLong(left); long R = Long.parseLong(right); int count = 0; // This loop is too slow and will time out. for (long i = L; i <= R; i++) { if (isSuperPalindrome(i)) { count++; } } return count; } private boolean isSuperPalindrome(long n) { if (!isPalindrome(n)) { return false; } long sqrtN = (long) Math.sqrt(n); if (sqrtN * sqrtN != n) { return false; } return isPalindrome(sqrtN); } private boolean isPalindrome(long n) { String s = String.valueOf(n); int left = 0, right = s.length() - 1; while (left < right) { if (s.charAt(left++) != s.charAt(right--)) { return false; } } return true; }}Complexity
Time
`O((R - L) * log(R))`. The loop runs `R - L` times. Inside the loop, `sqrt` takes `O(log(R))` time, and palindrome checks also take `O(log(R))` time (proportional to the number of digits). Given `R` can be up to `10^18`, this is far too slow.
Space
`O(log(R))` to store the string representation of the numbers for palindrome checks.
Trade-offs
Pros
Simple to understand and implement.
Cons
Extremely inefficient. The range
[left, right]can be up to[1, 10^18], making the loop infeasible. It will result in a "Time Limit Exceeded" error on any reasonably large test case.
Solutions
Solution
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; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.