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.
A significant improvement over the first approach is to change the iteration space. Instead of checking every number S in the range [L, R], we can generate potential super-palindromes by iterating through possible roots P. If S is in the range [1, 10^18], its root P must be in the range [1, 10^9].
Algorithm
- Parse
leftandrightstrings tolongintegersLandR. - Initialize
countto 0. - Calculate the upper limit for the root
passqrt(R). - Iterate
pfrom1up to this limit. - Inside the loop:
- If
pis a palindrome:- Calculate
s = p * p. - If
s > R, break the loop. - If
s >= Landsis also a palindrome, incrementcount.
- Calculate
- If
- Return
count.
Walkthrough
The core idea is to iterate through all integers p from 1 up to 10^9 (the square root of the maximum possible value of right). For each integer p, we first check if it's a palindrome. If p is a palindrome, we calculate its square, s = p * p. We must handle potential overflows, although for p <= 10^9, p*p fits within a long. If s exceeds the upper bound R, we can stop iterating because subsequent squares will also be too large. If s is within the range [L, R], we then check if s is also a palindrome. If both p and s are palindromes and s is in the required range, we increment our count. This approach drastically reduces the number of iterations from R - L (up to 10^18) to 10^9. However, 10^9 iterations are still too many for a typical time limit of a few seconds.
class Solution { public int superpalindromesInRange(String left, String right) { long L = Long.parseLong(left); long R = Long.parseLong(right); int count = 0; long limit = 1000000000L; // sqrt(10^18) = 10^9 // This loop is still too slow. for (long p = 1; p < limit; p++) { if (isPalindrome(p)) { long s = p * p; if (s > R) { break; } if (s >= L && isPalindrome(s)) { count++; } } } return count; } 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(sqrt(R) * log(R))`. The loop runs up to `10^9` times. The palindrome checks take `O(log(p))` and `O(log(p^2))`, which is `O(log(R))`. This is too slow.
Space
`O(log(R))` for palindrome checks.
Trade-offs
Pros
Much more efficient than the first approach by reducing the search space from
[L, R]to[1, sqrt(R)].
Cons
Still too slow. The loop runs up to
10^9times, which will cause a "Time Limit Exceeded" error.
The most efficient approach avoids checking non-palindromic numbers for the root P. Instead of iterating through all numbers up to 10^9 and checking if they are palindromes, we can directly generate only the palindromic numbers. The number of palindromes up to 10^9 is relatively small (around 200,000), making this approach feasible.
Algorithm
- Parse
leftandrightstrings tolongintegersLandR. - Initialize
countto 0. - Define a limit for the first half of the root,
LIMIT = 100000. - Odd-length roots: Loop
kfrom1toLIMIT.- Construct odd-length palindrome
pfromk. - Calculate
s = p * p. - If
s > R, break. - If
s >= LandisPalindrome(s), incrementcount.
- Construct odd-length palindrome
- Even-length roots: Loop
kfrom1toLIMIT.- Construct even-length palindrome
pfromk. - Calculate
s = p * p. - If
s > R, break. - If
s >= LandisPalindrome(s), incrementcount.
- Construct even-length palindrome
- Return
count.
Walkthrough
A palindrome is constructed from its first half. For example, from 123, we can construct the odd-length palindrome 12321 and the even-length palindrome 123321. The root P of a super-palindrome S <= 10^18 must be less than 10^9. A number less than 10^9 has at most 9 digits. The first half of a 9-digit palindrome has 5 digits (e.g., abcde for abcdedcba). The largest possible first half is 99999. Therefore, we only need to iterate through numbers k from 1 to 100,000 to form the first half of our palindromic roots. The algorithm proceeds as follows:
- Parse
leftandrighttolongsLandR. - Iterate
kfrom1to100,000. - Generate odd-length palindromes
P:- From
k, construct an odd-length palindromep. Fork=123,p=12321. - Calculate
s = p * p. - If
s > R, we can stop this loop as subsequent squares will be larger. - If
s >= LandisPalindrome(s), increment the count.
- From
- Generate even-length palindromes
P:- From
k, construct an even-length palindromep. Fork=123,p=123321. - Calculate
s = p * p. - If
s > R, stop this loop. - If
s >= LandisPalindrome(s), increment the count. This method drastically cuts down the number of candidates forPthat we need to check, leading to a very fast solution.
- From
class Solution { public int superpalindromesInRange(String left, String right) { long L = Long.parseLong(left); long R = Long.parseLong(right); int count = 0; int LIMIT = 100000; // Odd length palindromic roots for (int i = 1; i < LIMIT; i++) { String s = Integer.toString(i); StringBuilder reversedS = new StringBuilder(s).reverse(); String palindromeStr = s + reversedS.substring(1); long p = Long.parseLong(palindromeStr); long pSquare = p * p; if (pSquare > R) { break; } if (pSquare >= L && isPalindrome(pSquare)) { count++; } } // Even length palindromic roots for (int i = 1; i < LIMIT; i++) { String s = Integer.toString(i); String reversedS = new StringBuilder(s).reverse().toString(); String palindromeStr = s + reversedS; long p = Long.parseLong(palindromeStr); long pSquare = p * p; if (pSquare > R) { break; } if (pSquare >= L && isPalindrome(pSquare)) { count++; } } return count; } private boolean isPalindrome(long n) { String s = Long.toString(n); int left = 0; int right = s.length() - 1; while (left < right) { if (s.charAt(left++) != s.charAt(right--)) { return false; } } return true; }}Complexity
Time
`O(W * log(R))`, where `W` is the number of candidates for the first half of the root (`10^5` in this case). `log(R)` is the cost of palindrome checking (the number of digits in `R` is at most 18). The complexity is roughly `O(10^5 * 18)`, which is very fast.
Space
`O(log(R))` for storing string representations of numbers during palindrome generation and checking. This is effectively constant space as `log(R)` is small (at most 18).
Trade-offs
Pros
Highly efficient and passes within the time limits.
The number of candidates for the root
Pis very small (~2 * 10^5), making the number of checks minimal.
Cons
The logic for generating palindromes is slightly more complex than the brute-force approaches.
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; }}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() candi . add(p) 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) candi . add("1") candi . add("2") candi . add("3") 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// 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 ; } };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.