Super Palindromes - Practice Coding Problems

Super Palindromes - Problem

A super-palindrome is a positive integer that satisfies two conditions:

It is a palindrome (reads the same forwards and backwards)
It is the square of a palindrome

Given two positive integers left and right represented as strings, return the number of super-palindromes in the inclusive range [left, right].

Example: If we have a palindrome like 11, its square is 121, which is also a palindrome. Therefore, 121 is a super-palindrome.

Input & Output

Example 1 — Small Range

$ Input: left = "1", right = "10"

› Output: 2

💡 Note: Super-palindromes in [1,10]: 4 (2² and both 4,2 are palindromes) and 9 (3² and both 9,3 are palindromes)

Example 2 — Larger Range

$ Input: left = "1", right = "1000"

› Output: 4

💡 Note: Super-palindromes: 1 (1²), 4 (2²), 9 (3²), and 121 (11²). All are palindromes and squares of palindromes.

Example 3 — High Range

$ Input: left = "100", right = "200"

› Output: 1

💡 Note: Only 121 (11²) is a super-palindrome in range [100,200]. 121 is palindrome and 11 is palindrome.

Constraints

1 ≤ int(left) ≤ int(right) ≤ 10¹⁸
left and right consist of only digits
left and right will not have leading zeros

Visualization

Tap to expand

Understanding the Visualization

Input

Range [left, right] to search for super-palindromes

Process

Find numbers that are palindromes AND squares of palindromes

Output

Count of super-palindromes in the range

Key Takeaway

🎯 Key Insight: Generate palindromes first, then check if their squares are also palindromes - much more efficient than checking every number!

Asked in

G Google 15 f Facebook 8

The key insight is to generate palindromes first instead of checking every number in the range. Generate palindromes up to sqrt(right), square them, and check if results are palindromes within range. Best approach uses palindrome generation with Time: O(sqrt(R) × log(R)), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Check Every Number	O(n × m)	O(1)	Check every number in range to see if it's a super-palindrome
Generate Palindromes First	O(sqrt(R) × log(R))	O(1)	Generate palindromes, square them, check if squares are also palindromes

Brute Force Check Every Number — Algorithm Steps

Step 1: Iterate through every number from left to right
Step 2: For each number, check if it's a palindrome
Step 3: Check if square root is integer and palindrome
Step 4: Count valid super-palindromes

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Range

Iterate through every number from left to right

Test Palindrome

Check if number is palindrome and square of palindrome

Count Valid

Count numbers that satisfy both conditions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int isPalindrome(char* s) {
    int len = strlen(s);
    for (int i = 0; i < len / 2; i++) {
        if (s[i] != s[len - 1 - i]) {
            return 0;
        }
    }
    return 1;
}

int solution(char* left, char* right) {
    int count = 0;
    long long leftNum = atoll(left);
    long long rightNum = atoll(right);
    
    for (long long num = leftNum; num <= rightNum; num++) {
        char numStr[20];
        sprintf(numStr, "%lld", num);
        
        if (isPalindrome(numStr)) {
            long long sqrtNum = (long long) sqrt(num);
            if (sqrtNum * sqrtNum == num) {
                char sqrtStr[20];
                sprintf(sqrtStr, "%lld", sqrtNum);
                if (isPalindrome(sqrtStr)) {
                    count++;
                }
            }
        }
    }
    
    return count;
}

int main() {
    char left[20], right[20];
    fgets(left, sizeof(left), stdin);
    fgets(right, sizeof(right), stdin);
    left[strcspn(left, "\n")] = 0;
    right[strcspn(right, "\n")] = 0;
    
    int result = solution(left, right);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

n is range size, m is average digits per number for palindrome checking

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

18.5K Views

Medium Frequency

~45 min Avg. Time

432 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Check Every Number — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler