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

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.

Code

C++
 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;
    }
};
Java
 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.toString();
            long v = Long.parseLong(pal);
            long sq = v * v;
            if (sq > r) break;
            if (sq >= l && isPalindrome(sq)) ++ans;
        }
        return (int)ans;
    }
}
Kotlin
 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
    }
}
Python
 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
Rust
 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
    }
}
TypeScript
 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;
}

Explanation

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.

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)