Problem

Let’s say a positive integer is a super-palindrome if it is a palindrome, and it is also the square of a palindrome.

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

Examples

Example 1

1
2
3
4

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

1
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.

Solution

Method 1 - Palindromic Root Enumeration

Intuition

We generate all palindromic numbers up to the square root of right, square them, and check if the result is a palindrome and within the range. Both odd and even length palindromes are considered.

Approach

We generate all palindromic numbers up to the square root of right, square them, and check if the result is a palindrome and within the range. We check both odd and even length palindromes.

Complexity

  • ⏰ Time complexity: O(N log N) where N is the number of palindromic roots generated (up to 2*10^5).
  • 🧺 Space complexity: O(1)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
public:
    bool isPalindrome(long long x) {
        string s = to_string(x);
        int l = 0, r = s.size() - 1;
        while (l < r) if (s[l++] != s[r--]) return false;
        return true;
    }
    int superpalindromesInRange(string left, string right) {
        long long l = stoll(left), r = stoll(right), ans = 0;
        // Odd length palindromes
        for (int k = 1; k < 100000; ++k) {
            string s = to_string(k), t = s;
            reverse(t.begin(), t.end() - 1);
            string pal = s + t.substr(1);
            long long v = stoll(pal);
            long long sq = v * v;
            if (sq > r) break;
            if (sq >= l && isPalindrome(sq)) ++ans;
        }
        // Even length palindromes
        for (int k = 1; k < 100000; ++k) {
            string s = to_string(k), t = s;
            reverse(t.begin(), t.end());
            string pal = s + t;
            long long v = stoll(pal);
            long long sq = v * v;
            if (sq > r) break;
            if (sq >= l && isPalindrome(sq)) ++ans;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    private boolean isPalindrome(long x) {
        String s = Long.toString(x);
        int l = 0, r = s.length() - 1;
        while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
        return true;
    }
    public int superpalindromesInRange(String left, String right) {
        long l = Long.parseLong(left), r = Long.parseLong(right), ans = 0;
        // Odd length palindromes
        for (int k = 1; k < 100000; ++k) {
            String s = Integer.toString(k);
            StringBuilder t = new StringBuilder(s).reverse();
            String pal = s + t.substring(1);
            long v = Long.parseLong(pal);
            long sq = v * v;
            if (sq > r) break;
            if (sq >= l && isPalindrome(sq)) ++ans;
        }
        // Even length palindromes
        for (int k = 1; k < 100000; ++k) {
            String s = Integer.toString(k);
            StringBuilder t = new StringBuilder(s).reverse();
            String pal = s + t;
            long v = Long.parseLong(pal);
            long sq = v * v;
            if (sq > r) break;
            if (sq >= l && isPalindrome(sq)) ++ans;
        }
        return (int)ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    private fun isPalindrome(x: Long): Boolean {
        val s = x.toString()
        return s == s.reversed()
    }
    fun superpalindromesInRange(left: String, right: String): Int {
        val l = left.toLong()
        val r = right.toLong()
        var ans = 0
        for (k in 1 until 100000) {
            val s = k.toString()
            val pal1 = (s + s.dropLast(1).reversed()).toLong()
            val sq1 = pal1 * pal1
            if (sq1 > r) break
            if (sq1 >= l && isPalindrome(sq1)) ans++
        }
        for (k in 1 until 100000) {
            val s = k.toString()
            val pal2 = (s + s.reversed()).toLong()
            val sq2 = pal2 * pal2
            if (sq2 > r) break
            if (sq2 >= l && isPalindrome(sq2)) ans++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def superpalindromesInRange(self, left: str, right: str) -> int:
        l, r = int(left), int(right)
        ans = 0
        # Odd length palindromes
        for k in range(1, 100000):
            s = str(k)
            pal = int(s + s[-2::-1])
            sq = pal * pal
            if sq > r: break
            if sq >= l and str(sq) == str(sq)[::-1]:
                ans += 1
        # Even length palindromes
        for k in range(1, 100000):
            s = str(k)
            pal = int(s + s[::-1])
            sq = pal * pal
            if sq > r: break
            if sq >= l and str(sq) == str(sq)[::-1]:
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

impl Solution {
    pub fn superpalindromes_in_range(left: String, right: String) -> i32 {
        let l = left.parse::<u64>().unwrap();
        let r = right.parse::<u64>().unwrap();
        let mut ans = 0;
        for k in 1..100_000 {
            let s = k.to_string();
            let pal1 = format!("{}{}", s, s.chars().rev().skip(1).collect::<String>());
            let v1 = pal1.parse::<u64>().unwrap();
            let sq1 = v1 * v1;
            if sq1 > r { break; }
            if sq1 >= l && sq1.to_string() == sq1.to_string().chars().rev().collect::<String>() {
                ans += 1;
            }
        }
        for k in 1..100_000 {
            let s = k.to_string();
            let pal2 = format!("{}{}", s, s.chars().rev().collect::<String>());
            let v2 = pal2.parse::<u64>().unwrap();
            let sq2 = v2 * v2;
            if sq2 > r { break; }
            if sq2 >= l && sq2.to_string() == sq2.to_string().chars().rev().collect::<String>() {
                ans += 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

function superpalindromesInRange(left: string, right: string): number {
    const l = BigInt(left), r = BigInt(right);
    let ans = 0;
    for (let k = 1; k < 100000; ++k) {
        const s = k.toString();
        const pal1 = BigInt(s + s.slice(0, -1).split('').reverse().join(''));
        const sq1 = pal1 * pal1;
        if (sq1 > r) break;
        if (sq1 >= l && sq1.toString() === sq1.toString().split('').reverse().join('')) ans++;
    }
    for (let k = 1; k < 100000; ++k) {
        const s = k.toString();
        const pal2 = BigInt(s + s.split('').reverse().join(''));
        const sq2 = pal2 * pal2;
        if (sq2 > r) break;
        if (sq2 >= l && sq2.toString() === sq2.toString().split('').reverse().join('')) ans++;
    }
    return ans;
}