Problem statement

https://leetcode.com/problems/prime-palindrome/

Solution

Here we need to iterate through palindromes, starting from the smallest one and return the first one, which is bigger than N. We need to use is_prime function to check if number is prime. Potential time complexity is O(N) if we assume that there exists enough palindromes, which works in practice: we check O(sqrt{N}) numbers with O(sqrt{N}) complexity to check if it is prime for each of them.

Also we can notice that palindrome of even length will always be divisible by 11, so there is no need to check them, except number 11 itself.

Complexity

Time complexity is O(N), space is O(1).

Code

class Solution:
    def primePalindrome(self, N):
        def is_prime(n):
            return n > 1 and all(n%d for d in range(2, int(n**.5) + 1))

        for L in range(1, 6):
            for half in range(10**(L - 1), 10**L):
                s = str(half)
                x = int(s + s[-2::-1])
                if x >= N and is_prime(x):
                    return min(x, 11) if N <= 11 else x