Super Palindromes solution and explanation
Google
9 more videos on this problem
Super Palindromes | Live Coding with Explanation | Leetcode - 906Algorithms Made Easy · 11:55 · 2K views
Super Palindromes | Strings | Maths | 906 LeetCode | LeetCode Explore | Day 08CodeWithSunny · 11:45 · 1K views
Super Palindromes | Leetcode 906 | LC 906 | Live coding session | Hard| Explore 8 May | MathCoding Decoded · 12:30 · 836 views
LeetCode 906. Super PalindromesHappy Coding · 15:02 · 811 views
LeetCode - 906. Super Palindromes | Day 8 May ChallengeAditya Mahajan · 10:54 · 704 views
Leetcode - Super Palindromes (Python)Timothy H Chang · 8:11 · 486 views
Daily Leetcode #403: May 08, 2021 - 906. Super PalindromesProgramming Live with Larry · 18:52 · 377 views
【每日一题】906. Super Palindromes, 1/6/2020Huifeng Guan · 24:05 · 377 views
Super Palindromes | LeetCode 906 | Coders CampCoders Camp · 9:58 · 281 views
LeetCode 每日一题 Daily Challenge 906 Super PalindromesMaxMing · 3:42 · 105 views
The problem
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.
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.
def is_palindrome(x):
s = str(x)
return s == s[::-1]
def superpalindromes_in_range(left: str, right: str) -> int:
L = int(left)
R = int(right)
MAGIC = 10**5 # Generate palindromes up to this range
count = 0
# odd length palindrome
for k in range(1, MAGIC):
s = str(k)
t = s + s[-2::-1] # create odd-length palindrome
v = int(t) ** 2
if v > R:
break
if v >= L and is_palindrome(v):
count += 1
# even length palindrome
for k in range(1, MAGIC):
s = str(k)
t = s + s[::-1] # create even-length palindrome
v = int(t) ** 2
if v > R:
break
if v >= L and is_palindrome(v):
count += 1
return count#include <iostream>
#include <string>
#include <cmath>
bool isPalindrome(long x) {
std::string s = std::to_string(x);
int n = s.size();
for (int i = 0; i < n / 2; ++i) {
if (s[i] != s[n - i - 1]) return false;
}
return true;
}
int superpalindromesInRange(std::string left, std::string right) {
long L = std::stol(left), R = std::stol(right);
const long MAGIC = 100000; // Generate palindromes up to this range
int count = 0;
// odd length palindromes
for (int k = 1; k < MAGIC; ++k) {
std::string s = std::to_string(k);
std::string t = s + std::string(s.rbegin() + 1, s.rend());
long v = std::stol(t);
v *= v;
if (v > R) break;
if (v >= L && isPalindrome(v)) {
count++;
}
}
// even length palindromes
for (int k = 1; k < MAGIC; ++k) {
std::string s = std::to_string(k);
std::string t = s + std::string(s.rbegin(), s.rend());
long v = std::stol(t);
v *= v;
if (v > R) break;
if (v >= L && isPalindrome(v)) {
count++;
}
}
return count;
}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.
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.
public class SuperPalindromes {
public boolean isPalindrome(long x) {
String s = Long.toString(x);
int n = s.length();
for (int i = 0; i < n / 2; i++) {
if (s.charAt(i) != s.charAt(n - i - 1)) return false;
}
return true;
}
public int superpalindromesInRange(String left, String right) {
long L = Long.parseLong(left);
long R = Long.parseLong(right);
final long MAGIC = 100000; // Generate palindromes up to this range
int count = 0;
// odd length palindromes
for (int k = 1; k < MAGIC; k++) {
String s = Integer.toString(k);
String t = s + new StringBuilder(s.substring(0, s.length() - 1)).reverse().toString();
long v = Long.parseLong(t);
v *= v;
if (v > R) break;
if (v >= L && isPalindrome(v)) {
count++;
}
}
// even length palindromes
for (int k = 1; k < MAGIC; k++) {
String s = Integer.toString(k);
String t = s + new StringBuilder(s).reverse().toString();
long v = Long.parseLong(t);
v *= v;
if (v > R) break;
if (v >= L && isPalindrome(v)) {
count++;
}
}
return count;
}
}function isPalindrome(x) {
let s = x.toString();
for (let i = 0, j = s.length - 1; i < j; i++, j--) {
if (s[i] !== s[j]) return false;
}
return true;
}
function superpalindromesInRange(left, right) {
const L = BigInt(left);
const R = BigInt(right);
const MAGIC = 100000n; // Generate palindromes up to this range
let count = 0;
// odd length palindromes
for (let k = 1n; k < MAGIC; k++) {
let s = k.toString();
let t = s + s.slice(0, -1).split('').reverse().join('');
let v = BigInt(t) ** 2n;
if (v > R) break;
if (v >= L && isPalindrome(v)) {
count++;
}
}
// even length palindromes
for (let k = 1n; k < MAGIC; k++) {
let s = k.toString();
let t = s + s.split('').reverse().join('');
let v = BigInt(t) ** 2n;
if (v > R) break;
if (v >= L && isPalindrome(v)) {
count++;
}
}
return count;
}The Java solution constructs palindromes by concisely appending mirrored parts of the string, akin to the methods in other language solutions. The range is checked by transforming these palindromes into numbers and ensuring their square values are in range and themselves palindromes.
Time Complexity: O(Magic * log(M)) where M is the limit (here MAGIC) for generating palindromes.
Space Complexity: O(1) indicating the fixed allocation of space for operations.
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:
const ps = Array(2e5).fill(0);
const init = (() => {
for (let i = 1; i <= 1e5; ++i) {
const s: string = i.toString();
const t1: string = s.split('').reverse().join('');
const t2: string = s.slice(0, -1).split('').reverse().join('');
ps[2 * i - 2] = parseInt(s + t1, 10);
ps[2 * i - 1] = parseInt(s + t2, 10);
}
})();
function superpalindromesInRange(left: string, right: string): number {
const l = BigInt(left);
const r = BigInt(right);
const isPalindrome = (x: bigint): boolean => {
const s: string = x.toString();
return s === s.split('').reverse().join('');
};
let ans = 0;
for (const p of ps) {
const x = BigInt(p) * BigInt(p);
if (x >= l && x <= r && isPalindrome(x)) {
++ans;
}
}
return ans;
}var ps [2 * 100000]int64
func init() {
for i := 1; i <= 100000; i++ {
s := strconv.Itoa(i)
t1 := reverseString(s)
t2 := reverseString(s[:len(s)-1])
ps[2*i-2], _ = strconv.ParseInt(s+t1, 10, 64)
ps[2*i-1], _ = strconv.ParseInt(s+t2, 10, 64)
}
}
func reverseString(s string) string {
cs := []rune(s)
for i, j := 0, len(cs)-1; i < j; i, j = i+1, j-1 {
cs[i], cs[j] = cs[j], cs[i]
}
return string(cs)
}
func superpalindromesInRange(left string, right string) (ans int) {
l, _ := strconv.ParseInt(left, 10, 64)
r, _ := strconv.ParseInt(right, 10, 64)
isPalindrome := func(x int64) bool {
var y int64
for t := x; t > 0; t /= 10 {
y = y*10 + int64(t%10)
}
return x == y
}
for _, p := range ps {
x := p * p
if x >= l && x <= r && isPalindrome(x) {
ans++
}
}
return
}Complexity comparison
| 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) indicating the fixed allocation of space for operations. |
| Preprocessing + Enumeration | – |
Complexity analysis
| 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. |
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.