Super Palindromes

Problem Statement

In this problem, we are introduced to the concept of a super-palindrome. A super-palindrome is defined as a positive integer that not only reads the same forward and backward (making it a palindrome) but is also the square of another palindrome number. Given two positive integers, left and right, specified as string inputs, the task is to count the number of super-palindrome integers within the inclusive range [left, right]. For instance, if provided with the range "4" to "1000", we should count all integers meeting the super-palindrome criteria between 4 and 1000.

Examples

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 and Intuition

To tackle the problem of finding super-palindromes, consider the following approach:

1. Understanding Constraints and Inputs:

   • The inputs left and right specify the range and are given as strings. They could represent numbers as large as (10^{18} - 1), but always constitute valid integers without any leading zeros.
   • Our task is to interpret these strings as integers and work within the specified range.

2. Palindromes and Super-Palindromes:

   • A palindrome is a number that remains the same when its digits are reversed.
   • To find super-palindromes, one approach is to generate palindrome numbers, square them, and check if the result is also a palindrome and lies within the specified range.

3. Generating Palindromes:

   • Start by generating smaller palindrome numbers and gradually increase.
   • Check each generated palindrome if, upon squaring, it remains a palindrome and falls between left and right.

4. Efficient Checking:

   • Once a square exceeds right, stop the generation of higher palindromes as their squares will only be larger.
   • Efficient palindrome checking can be implemented to ensure the procedure remains optimal.

5. Result Compilation:

   • Keep a count of palindromes meeting the criteria.
   • This approach leverages mathematical properties of palindromes to ensure we efficiently traverse the possible candidates.

Example Intuition:

• For the range "4" to "1000":
  • Generate small palindromes like 1, 2, 3,..., check their squares.
  • The numbers 4 (2^2), 9 (3^3), 121 (11^2), and 484 (22^2) are identified as they are squares of palindromes and are themselves palindromes within the range.
  • The square of the palindrome 26 is 676, but since 26 is not a palindrome, 676 doesn't qualify as a super-palindrome.

Solutions

class Solution {
    public int countSuperpalindromesInRange(String low, String high) {
        long start = Long.parseLong(low);
        long end = Long.parseLong(high);
        int LIMIT = 100000;
        int result = 0;
    
        // Check for odd lengths
        for (int i = 1; i < LIMIT; ++i) {
            StringBuilder candidate = new StringBuilder(Integer.toString(i));
            for (int j = candidate.length() - 2; j >= 0; --j)
                candidate.append(candidate.charAt(j));
            long number = Long.parseLong(candidate.toString());
            number *= number;
            if (number > end) break;
            if (number >= start && checkPalindrome(number)) result++;
        }
    
        // Check for even lengths
        for (int i = 1; i < LIMIT; ++i) {
            StringBuilder candidate = new StringBuilder(Integer.toString(i));
            for (int j = candidate.length() - 1; j >= 0; --j)
                candidate.append(candidate.charAt(j));
            long number = Long.parseLong(candidate.toString());
            number *= number;
            if (number > end) break;
            if (number >= start && checkPalindrome(number)) result++;
        }
    
        return result;
    }
    
    public boolean checkPalindrome(long x) {
        return x == reverseNumber(x);
    }
    
    public long reverseNumber(long x) {
        long reversed = 0;
        while (x > 0) {
            reversed = 10 * reversed + x % 10;
            x /= 10;
        }
    
        return reversed;
    }
}