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.Problem Overview: Given two numbers L and R, count how many numbers in this range are super palindromes. A super palindrome is a number that is itself a palindrome and also the square of another palindrome. The key challenge is the huge range (up to 1018), which makes direct enumeration impossible.
Approach 1: Brute Force Generation of Palindromes (Enumeration, ~O(k * d))
Instead of checking every number between L and R, generate palindromic numbers as potential square roots. Compute sqrt(R), then enumerate palindromes up to this bound. For each generated palindrome p, compute p * p and check two conditions: the square lies within [L, R] and the square itself is also a palindrome. Palindrome checks use string comparison from both ends. If the maximum root is around 109, the number of palindromes is only about 105, making enumeration feasible. Time complexity is roughly O(k * d) where k is the number of generated palindromes and d is the digit length for palindrome checks, with O(1) extra space.
This approach relies heavily on enumeration and simple math observations about square roots. It dramatically reduces the search space compared to scanning the entire interval.
Approach 2: Iterative Palindrome Construction (Optimized Enumeration, O(k))
Construct palindromes directly by building them from a numeric prefix. Iterate over a prefix i, convert it to a string, and mirror it to produce both odd-length and even-length palindromes. Each constructed value represents a palindromic root candidate. Square the value and check whether the result lies inside [L, R] and remains a palindrome.
The insight is that every palindrome can be formed by mirroring a prefix. This avoids expensive checks over arbitrary numbers and guarantees that only valid palindrome roots are generated. Since only about 100k candidates exist below 109, the algorithm runs quickly. Time complexity is O(k) for generating and validating candidates, with O(1) auxiliary space.
This method is essentially structured enumeration combined with digit manipulation. It is the standard competitive programming solution because it prunes the search space aggressively.
Recommended for interviews: Interviewers expect the palindrome-root enumeration approach. A naive brute force over the numeric range demonstrates understanding of the problem definition but fails on constraints. Constructing palindromes iteratively and squaring them shows stronger algorithmic reasoning and familiarity with math-based pruning techniques.
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.
This 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.
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.
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.
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.
JavaScript
Java
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.
According to the problem description, we assume that the super palindrome number x = p^2 \in [1, 10^{18}), where p is a palindrome number, so p \in [1, 10^9). We can enumerate the first half of the palindrome number p, then reverse it, and concatenate it to get all palindrome numbers, which are recorded in the array ps.
Next, we traverse the array ps. For each p, we calculate p^2, check whether it is in the interval [L, R], and also check whether p^2 is a palindrome number. If it is, the answer is incremented by one.
After the traversal, return the answer.
The time complexity is O(M^{\frac{1}{4}} times log M), and the space complexity is O(M^{\frac{1}{4}}). Where M is the upper bound of L and R, and in this problem, M leq 10^{18}.
Similar problems:
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Generation of Palindromes | 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. |
| Iterative Palindrome Construction | 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. |
| Preprocessing + Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Generation of Palindromes | O(k * d) | O(1) | When enumerating palindrome roots up to sqrt(R) and validating squares with simple string checks. |
| Iterative Palindrome Construction | O(k) | O(1) | Best for large ranges up to 10^18 where generating palindromes via mirrored prefixes minimizes candidates. |
Super Palindromes | Live Coding with Explanation | Leetcode - 906 • Algorithms Made Easy • 2,187 views views
Watch 9 more video solutions →Practice Super Palindromes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor