Super Palindromes - Video Solutions

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 10¹⁸), 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 10⁹, the number of palindromes is only about 10⁵, 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 10⁹, 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.