Super Palindromes

hard math palindrome enumeration

Problem

A super-palindrome is a number that is itself a palindrome and is also the square of a palindrome. Given two positive integers left and right (as strings), return the count of super-palindromes in the inclusive range [left, right]. Because the answer's square root must be a palindrome, we enumerate palindromic roots, square each one, and check whether the square lands in range and is a palindrome.

Inputleft = "4", right = "1000"

Output4

The super-palindromes in [4, 1000] are 4 (=2²), 9 (=3²), 121 (=11²), and 484 (=22²).

left

right

def superpalindromes(left, right):
    lo, hi = int(left), int(right)
    is_pal = lambda s: s == s[::-1]
    count = 0
    # Build palindromic roots from a half, then square.
    for half in range(1, 100000):
        s = str(half)
        # odd length: mirror without the last digit
        root = int(s + s[-2::-1])
        sq = root * root
        if sq > hi:
            break
        if sq >= lo and is_pal(str(sq)):
            count += 1
        # even length: mirror the whole half
        root = int(s + s[::-1])
        sq = root * root
        if lo <= sq <= hi and is_pal(str(sq)):
            count += 1
    return count

function superpalindromes(left, right) {
  const lo = BigInt(left), hi = BigInt(right);
  const isPal = (s) => s === s.split("").reverse().join("");
  let count = 0;
  for (let half = 1n; half < 100000n; half++) {
    const s = half.toString();
    // odd length: mirror without the last digit
    let root = BigInt(s + s.slice(0, -1).split("").reverse().join(""));
    let sq = root * root;
    if (sq > hi) break;
    if (sq >= lo && isPal(sq.toString())) count++;
    // even length: mirror the whole half
    root = BigInt(s + s.split("").reverse().join(""));
    sq = root * root;
    if (sq >= lo && sq <= hi && isPal(sq.toString())) count++;
  }
  return count;
}

class Solution {
    boolean isPal(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) if (s.charAt(i++) != s.charAt(j--)) return false;
        return true;
    }
    public int superpalindromesInRange(String left, String right) {
        long lo = Long.parseLong(left), hi = Long.parseLong(right);
        int count = 0;
        for (long half = 1; half < 100000; half++) {
            String s = Long.toString(half);
            String odd = s + new StringBuilder(s.substring(0, s.length() - 1)).reverse();
            long sq = Long.parseLong(odd); sq *= sq;
            if (sq > hi) break;
            if (sq >= lo && isPal(Long.toString(sq))) count++;
            String even = s + new StringBuilder(s).reverse();
            sq = Long.parseLong(even); sq *= sq;
            if (sq >= lo && sq <= hi && isPal(Long.toString(sq))) count++;
        }
        return count;
    }
}

class Solution {
    bool isPal(const string& s) {
        for (int i = 0, j = (int)s.size() - 1; i < j; i++, j--)
            if (s[i] != s[j]) return false;
        return true;
    }
public:
    int superpalindromesInRange(string left, string right) {
        long long lo = stoll(left), hi = stoll(right);
        int count = 0;
        for (long long half = 1; half < 100000; half++) {
            string s = to_string(half);
            string odd = s + string(s.rbegin() + 1, s.rend());
            long long r = stoll(odd), sq = r * r;
            if (sq > hi) break;
            if (sq >= lo && isPal(to_string(sq))) count++;
            string even = s + string(s.rbegin(), s.rend());
            r = stoll(even); sq = r * r;
            if (sq >= lo && sq <= hi && isPal(to_string(sq))) count++;
        }
        return count;
    }
};

Explanation

A super-palindrome must be a palindrome AND be the square of a palindrome. Checking every number in a huge range is far too slow, so we flip the problem around: instead of searching for the squares, we generate the palindromic roots and square them.

Because a super-palindrome's square root is itself a palindrome, the roots are sparse. We build palindromes from a half: take a number like 12 and mirror it to make 121 (odd length) or 1221 (even length). That produces every palindromic root in order without gaps.

For each generated root we compute sq = root * root. If sq already exceeds hi we stop, since squares only grow. Otherwise, if sq is in [lo, hi] and sq is itself a palindrome, we count it.

Example for [4, 1000]: root 2 → 4 (palindrome, in range), root 3 → 9, root 11 → 121, root 22 → 484. That gives the four super-palindromes.

This works because squaring the few palindromic roots is enough to find every candidate, and we only have to verify each square is a palindrome and lands in range.

Time: O(√R^1/2 · log R) Space: O(log R)