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 <= 18left 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.In #906 Super Palindromes, a number is considered a super palindrome if it is a palindrome and also the square of another palindrome. Instead of checking every number in the given range, the key idea is to generate palindromic roots first. Since the square must lie within the range, you only need to consider palindromic numbers up to sqrt(R).
Use enumeration to construct palindromes by building them from half of their digits (handling both odd and even lengths). For each generated palindrome, compute its square and verify two conditions: the square lies within the given range and the square itself is also a palindrome. This significantly reduces the search space compared to brute force.
This approach leverages mathematical constraints and palindrome generation to keep the computation efficient. The number of palindromic roots is limited, making the solution feasible even for very large ranges.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Enumerate Palindromic Roots and Check Squares | O(P) | O(1) |
NeetCode
This approach involves generating palindromes within a certain range, then squaring these palindromes and checking if the result is also a palindrome and within the given range. We generate palindromic numbers using digit manipulation and check each step if they meet the conditions.
Time Complexity: O(Magic * log(M)) where M is the limit (in this case, MAGIC) for generating palindromes.
Space Complexity: O(1), since we only use a fixed amount of extra space.
1def is_palindrome(x):
2 s = str(x)
3 return s == s[::-1]
4
5
6def superpalindromes_in_range(left: str, right: str) -> int:
7 L = int(left)
8 R = int(right)
9 MAGIC = 10**5 # Generate palindromes up to this range
10 count = 0
11
12 # odd length palindrome
13 for k in range(1, MAGIC):
14 s = str(k)
15 t = s + s[-2::-1] # create odd-length palindrome
16 v = int(t) ** 2
17 if v > R:
18 break
19 if v >= L and is_palindrome(v):
20 count += 1
21
22 # even length palindrome
23 for k in range(1, MAGIC):
24 s = str(k)
25 t = s + s[::-1] # create even-length palindrome
26 v = int(t) ** 2
27 if v > R:
28 break
29 if v >= L and is_palindrome(v):
30 count += 1
31
32 return countThis Python code defines a function called superpalindromes_in_range that takes in two strings left and right as its parameters. The function checks all numbers formed by odd and even length palindromes up to a limit (specified by a magic number, here 10**5) to see if their squares lie within the specified range and are themselves palindromes. If so, the function increments a counter which is returned as the result.
In this method, instead of generating palindromes up to a specific length, we iteratively construct them by appending mirrored sections. The main difference from the first approach is the construction and early exit mechanism based on the calculated square exceeding the right bound.
Time Complexity: O(Magic * log(M)) where M is the limit (here MAGIC) for generating palindromes.
Space Complexity: O(1) because of the absence of additional dynamic storage.
1function isPalindrome(x) {
2
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems similar to Super Palindromes can appear in FAANG-style interviews because they test mathematical insight, efficient enumeration, and optimization over brute force. Interviewers often expect candidates to reduce the search space using properties like palindromes and square roots.
The optimal approach is to generate palindromic numbers as potential square roots and then check whether their squares are also palindromes within the given range. This avoids brute force over the entire range. By limiting generation up to sqrt(R), the search space becomes manageable.
No complex data structure is required for this problem. Most solutions rely on mathematical generation of palindromes and simple string or numeric checks to verify whether a number is a palindrome.
Checking every number in the range would be infeasible because the range can go up to very large values. Generating palindromic roots ensures that only valid candidates are considered. Their squares are then tested for both range constraints and palindrome properties.
This JavaScript implementation follows the same algorithm of iteratively building palindromes using mirrored string operations and checks whether the resulting squares fall within the range and are palindromic. It makes use of BigInt for handling large numbers due to JavaScript's number size limits.