Skip to main content
Talentd

Super Palindromes - Solution & Explanation

HardMathEnumeration12 min readAsked at: Google
Practice this problem

Problem Statement

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.

Approach Overview

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.

Approach 1: Brute Force Generation of Palindromes

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Iterative Palindrome Construction

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.

Code

JavaScriptJava

JavaScript

Java

Complexity

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.

Try this approach in the editor →

Approach 3: Preprocessing + Enumeration

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:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Generation of PalindromesO(k * d)O(1)When enumerating palindrome roots up to sqrt(R) and validating squares with simple string checks.
Iterative Palindrome ConstructionO(k)O(1)Best for large ranges up to 10^18 where generating palindromes via mirrored prefixes minimizes candidates.

Video Solution

Super Palindromes | Live Coding with Explanation | Leetcode - 906 • Algorithms Made Easy • 2,199 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Super Palindromes easy or hard?
Super Palindromes is categorized as a Hard problem because the brute force idea fails under large constraints. The difficulty lies in recognizing that you should enumerate palindrome roots instead of checking every number in the range. Once the mathematical insight is applied, the implementation becomes manageable.
Super Palindromes Python/Java solution
Python, Java, C++, and JavaScript solutions typically build palindrome roots by mirroring prefixes. Each generated root is squared and tested for palindrome properties using string comparison. This approach keeps memory usage constant and handles the 10^18 constraint efficiently.
How to solve Super Palindromes in O(n)?
Construct palindromes directly from prefixes instead of scanning numbers. For each prefix, mirror it to produce odd and even length palindromes, treat them as roots, and square them. If the square lies within [L, R] and remains a palindrome, increment the count. This enumeration-based method keeps the candidate set small and efficient.
What is the best approach for Super Palindromes?
The most effective approach generates palindromic numbers as potential square roots and checks whether their squares are also palindromes within the given range. This reduces the search space from up to 10^18 numbers to roughly 10^5 palindrome candidates. The technique relies on enumerating palindrome roots and validating their squared values.
Is Super Palindromes asked at Google/Amazon/Meta?
Palindrome and number construction problems frequently appear in interviews at companies like Google, Amazon, and Meta. While this exact problem may not appear often, the pattern of generating valid numbers through mathematical constraints and pruning the search space is a common interview theme.
What data structure is used in Super Palindromes?
The solution mainly relies on string manipulation and numeric operations rather than complex data structures. Palindromes are generated using string mirroring, and validation uses two-pointer or reverse-string checks. The core idea is mathematical enumeration rather than data structure optimization.
What is the time complexity of Super Palindromes?
The optimized solution runs in about O(k), where k is the number of palindromic roots below sqrt(R). Since R can be up to 10^18, the maximum root is 10^9, but the count of palindromes under this limit is only around 100,000. Each candidate requires constant-time squaring and a digit-level palindrome check.

Ready to solve this problem?

Practice Super Palindromes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer