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