Problem Explanation

In the problem, we are asked to count Super-Palindromes between two given positive integers L and R. A positive integer is called a Super-Palindrome if it is a Palindrome and it is a square of a palindrome as well.

A Palindrome is a string which is similar when reading from start to end and end to start. e.g. "121", "12321", "1"

Solution Approach

If we analyze the problem, it is quite clear that we need to find all the palindrome numbers between sqrt(L) and sqrt(R) then check if the square of that number is also a palindrome.

The time complexity of this program is O(sqrt(n)) and space complexity is O(1).

Let's take an example to understand the approach:

Example 1: Input: L = "4", R = "1000" Output: 4

The numbers between sqrt(L) = sqrt(4) = 2 and sqrt(R) = sqrt(1000) = 31 are 2, 3, 11, 22, 121, 111, 121, 222, 232,......, 313.

Among these 11, 22, 111, 121, 212 are palindromes. Their squares are 121, 484, 12321, 14641, 44944 which are also palindromes. Therefore we conclude that there are 4 superpalindromes in the range.

Python Solution

1
2
3class Solution:
4    def superpalindromesInRange(self, L: str, R: str) -> int:
5        def is_palindrome(n):
6            return str(n) == str(n)[::-1]
7        
8        def next_palindrome(n):
9            s = str(n)
10            l = len(s)
11            half = s[:l // 2]
12            ret = int(half + s[(l - 1) // 2] + half[::-1])
13            if ret < n:
14                return int(str(int(s[:l // 2 + 1]) + (s[:l // 2 + 1][::-1])[l%2:]))
15            return ret
16                
17        l, r = int(L), int(R)
18        lb, ub = int(l ** 0.5), int((r + 1) ** 0.5) 
19        ans = lb * lb == l 
20        if lb * lb != l:
21            lb = next_palindrome(lb)
22        for x in range(lb, ub + 1):
23            if is_palindrome(x ** 2):
24                ans += 1 
25            x = next_palindrome(x)
26                
27        return ans

Java Solution

1
2
3class Solution {
4    public int superpalindromesInRange(String L, String R) {
5        long l = Long.parseLong(L), r = Long.parseLong(R);
6        int cnt = 0;
7        for (long i = (long)Math.ceil(Math.sqrt(l)); i <= (long)Math.sqrt(r);) {
8            long palindrome = updateToNextPalindrom(i);
9            if (Math.sqrt(palindrome) == Math.floor(Math.sqrt(palindrome)) && isPalindrom(String.valueOf(palindrome))) cnt++;
10            i++;
11        }
12        return cnt;
13    }
14    
15    private boolean isPalindrom(String s) {
16        int i = 0, j = s.length();
17        while (i < j) {
18            if (s.charAt(i++) != s.charAt(j--)) return false;
19        }
20        return true;
21    }
22
23    private long updateToNextPalindrom(long n) {
24        char[] s = String.valueOf(n).toCharArray();
25        int len = s.length;
26        for (int i = len / 2; i < len; i++) {
27            s[i] = s[len - i - 1];
28        }
29        long ret = Long.parseLong(new String(s));
30        if (ret < n) {
31            int half = Integer.parseInt(new String(s, 0, len / 2 + 1));
32            half++;
33            char[] halfArr = String.valueOf(half).toCharArray();
34            for (int i = 0; i <= len / 2; i++) {
35                s[i] = halfArr[i];
36            }
37            for (int i = len / 2; i < len; i++) {
38                s[i] = s[len - i - 1];
39            }
40            ret = Long.parseLong(new String(s));
41        }
42        return ret;
43    }
44}
45

Note: Unfortunately, I am not proficient in JavaScript, C++, C#. However, the logic would remain the same; only syntax would differ.# JavaScript Solution

JavaScript solution for this problem goes like this:

We keep generating next higher palindrome numbers, check whether the square of the palindrome is a palindrome and also lies within the given range.

To get next palindrome, we can do that by splitting the number half, reverse it and attach it to the number. Increment the number if it is smaller than the current number.

Here is the JavaScript Solution for the problem:

1
2javascript
3function superpalindromesInRange(left, right) {
4    let L = parseInt(left), R = parseInt(right);
5    let LOW = Math.floor(Math.sqrt(L)), HIGH = Math.ceil(Math.sqrt(R));
6    let cnt = 0;
7
8    for(let i = LOW; i <= HIGH;){
9        let p = createPalindrome(i);
10        if (p > i) i = p;
11        else {
12            if (p*p <= R && isPalindrome(p*p)) cnt++; 
13            i = nextNumber(i);
14        }
15    }
16    return cnt;
17};
18
19function createPalindrome(n) {
20    let s = n.toString().split('');
21    let len = s.length;
22    let ret = s.slice(0, Math.floor(len/2)).concat(s[Math.floor((len - 1)/2)]).concat(s.slice(0, Math.floor(len/2)).reverse()).join('');
23    return parseInt(ret);
24}
25
26function nextNumber(n) {
27    let len = n.toString().length;
28    let increment = Math.pow(10, Math.floor(len/2));
29    n = Math.floor(n / increment) * increment + increment;
30    return n;
31};
32
33function isPalindrome(n) {
34    let s = n.toString();
35    let len = s.length;
36    for(let i = 0; i < len / 2; i++) {
37        if(s[i] !== s[len - 1 - i]) {
38            return false;
39        }
40    }
41    return true;
42};

In all solutions, the key idea for counting super-palindromes is to generate palindrome candidates and filter out those that are not super-palindromes. This approach significantly reduces the search space and allows for efficient computation.