Leetcode 866: Prime Palindrome

Given an integer n, return the smallest prime palindrome greater than or equal to n.

An integer is prime if it has exactly two divisors: 1 and itself. Note that 1 is not a prime number.

• For example, 2, 3, 5, 7, 11, and 13 are all primes.

An integer is a palindrome if it reads the same from left to right as it does from right to left.

• For example, 101 and 12321 are palindromes.

The test cases are generated so that the answer always exists and is in the range [2, 2 * 108].

Example 1:

Input: n = 6
Output: 7

Example 2:

Input: n = 8
Output: 11

Example 3:

Input: n = 13
Output: 101

Constraints:

• 1 <= n <= 10^8

Problem Analysis:

If we iterate check every number from 1 to 10⁸, it will timeout.

As the answer must be a palindrome, so we only need to iterate from 1 to 10⁴.

And there is a trick that if the palindrome has even number of digits, the palindrome can be divided by 11. For simplicity, here we give a uncompleted explanation. Assume the palindrome x has even number of digits n, x_i is the ith digit, the sum of digits at odd positions sum_odd = x_1 + x_3 + … + x_n-1, sum of digits at even positions sum_even = x_2 + x_4 + … + x_n. sum_odd-sum_even = x_1 + x_3 + x_n-1-(x_2 + x_4 + … + x_n) = (x_1-x_n) + (x_3-x_n-2) + … (x_n-1-x_2) = 0. With this specific property, we can finally get the palindrome number x can be divided by 11.

So we can get 11 is the only even length palindrome that is a prime, and then we only need to check the palindromes with odd length.

Solution

class Solution {
public:
    int primePalindrome(int n) {
        if (n >= 8 && n <= 11) return 11;

        for (int i = 1; i < 100000; ++i) {
            string s = to_string(i);
            string r(s.rbegin(), s.rend());
            int x = stoi(s + r.substr(1));
            if (isPrime(x) && x >= n) return x;
        }

        return -1;
    }

    bool isPrime(int x) {
        if (x < 2 || x % 2 == 0) return x == 2;
        for (int i = 3; i * i <= x; i += 2) {
            if (x % i == 0) return false;
        }

        return true;
    }
};

Time complexity is O(n)

Space complexity is O(1)