906. Super Palindromes

Description

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 of super-palindromes integers in the inclusive range [left, right].

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, 10¹⁸ - 1].
left is less than or equal to right.

Solutions

Solution 1: Preprocessing + Enumeration

According to the problem description, we assume that the super palindrome number $x = p^2 \in [1, 10^{18})$, where $p$ is a palindrome number, so $p \in [1, 10^9)$. We can enumerate the first half of the palindrome number $p$, then reverse it, and concatenate it to get all palindrome numbers, which are recorded in the array $ps$.

Next, we traverse the array $ps$. For each $p$, we calculate $p^2$, check whether it is in the interval $[L, R]$, and also check whether $p^2$ is a palindrome number. If it is, the answer is incremented by one.

After the traversal, return the answer.

The time complexity is $O(M^{\frac{1}{4}} \times \log M)$, and the space complexity is $O(M^{\frac{1}{4}})$. Where $M$ is the upper bound of $L$ and $R$, and in this problem, $M \leq 10^{18}$.

Similar problems:

2967. Minimum Cost to Make Array Equalindromic

Python3JavaC++GoTypeScript

ps = []
for i in range(1, 10**5 + 1):
    s = str(i)
    t1 = s[::-1]
    t2 = s[:-1][::-1]
    ps.append(int(s + t1))
    ps.append(int(s + t2))


class Solution:
    def superpalindromesInRange(self, left: str, right: str) -> int:
        def is_palindrome(x: int) -> bool:
            y, t = 0, x
            while t:
                y = y * 10 + t % 10
                t //= 10
            return x == y

        l, r = int(left), int(right)
        return sum(l <= x <= r and is_palindrome(x) for x in map(lambda x: x * x, ps))

class Solution {
    private static long[] ps;

    static {
        ps = new long[2 * (int) 1e5];
        for (int i = 1; i <= 1e5; i++) {
            String s = Integer.toString(i);
            String t1 = new StringBuilder(s).reverse().toString();
            String t2 = new StringBuilder(s.substring(0, s.length() - 1)).reverse().toString();
            ps[2 * i - 2] = Long.parseLong(s + t1);
            ps[2 * i - 1] = Long.parseLong(s + t2);
        }
    }

    public int superpalindromesInRange(String left, String right) {
        long l = Long.parseLong(left);
        long r = Long.parseLong(right);
        int ans = 0;
        for (long p : ps) {
            long x = p * p;
            if (x >= l && x <= r && isPalindrome(x)) {
                ++ans;
            }
        }
        return ans;
    }

    private boolean isPalindrome(long x) {
        long y = 0;
        for (long t = x; t > 0; t /= 10) {
            y = y * 10 + t % 10;
        }
        return x == y;
    }
}

using ll = unsigned long long;

ll ps[2 * 100000];

int init = [] {
    for (int i = 1; i <= 100000; i++) {
        string s = to_string(i);
        string t1 = s;
        reverse(t1.begin(), t1.end());
        string t2 = s.substr(0, s.length() - 1);
        reverse(t2.begin(), t2.end());
        ps[2 * i - 2] = stoll(s + t1);
        ps[2 * i - 1] = stoll(s + t2);
    }
    return 0;
}();

class Solution {
public:
    int superpalindromesInRange(string left, string right) {
        ll l = stoll(left), r = stoll(right);
        int ans = 0;
        for (ll p : ps) {
            ll x = p * p;
            if (x >= l && x <= r && is_palindrome(x)) {
                ++ans;
            }
        }
        return ans;
    }

    bool is_palindrome(ll x) {
        ll y = 0;
        for (ll t = x; t; t /= 10) {
            y = y * 10 + t % 10;
        }
        return x == y;
    }
};

var ps [2 * 100000]int64

func init() {
    for i := 1; i <= 100000; i++ {
        s := strconv.Itoa(i)
        t1 := reverseString(s)
        t2 := reverseString(s[:len(s)-1])
        ps[2*i-2], _ = strconv.ParseInt(s+t1, 10, 64)
        ps[2*i-1], _ = strconv.ParseInt(s+t2, 10, 64)
    }
}

func reverseString(s string) string {
    cs := []rune(s)
    for i, j := 0, len(cs)-1; i < j; i, j = i+1, j-1 {
        cs[i], cs[j] = cs[j], cs[i]
    }
    return string(cs)
}

func superpalindromesInRange(left string, right string) (ans int) {
    l, _ := strconv.ParseInt(left, 10, 64)
    r, _ := strconv.ParseInt(right, 10, 64)
    isPalindrome := func(x int64) bool {
        var y int64
        for t := x; t > 0; t /= 10 {
            y = y*10 + int64(t%10)
        }
        return x == y
    }
    for _, p := range ps {
        x := p * p
        if x >= l && x <= r && isPalindrome(x) {
            ans++
        }
    }
    return
}

const ps = Array(2e5).fill(0);

const init = (() => {
    for (let i = 1; i <= 1e5; ++i) {
        const s: string = i.toString();
        const t1: string = s.split('').reverse().join('');
        const t2: string = s.slice(0, -1).split('').reverse().join('');
        ps[2 * i - 2] = parseInt(s + t1, 10);
        ps[2 * i - 1] = parseInt(s + t2, 10);
    }
})();

function superpalindromesInRange(left: string, right: string): number {
    const l = BigInt(left);
    const r = BigInt(right);
    const isPalindrome = (x: bigint): boolean => {
        const s: string = x.toString();
        return s === s.split('').reverse().join('');
    };
    let ans = 0;
    for (const p of ps) {
        const x = BigInt(p) * BigInt(p);
        if (x >= l && x <= r && isPalindrome(x)) {
            ++ans;
        }
    }
    return ans;
}

906. Super Palindromes

Description

Solutions

Solution 1: Preprocessing + Enumeration

Comments