Leetcode 866. Prime Palindrome

Problem Explanation

The problem asks us to find the smallest prime palindrome larger or equal to a given number. That means we need to find a number that is both a palindrome and prime which is greater than or equal to the input number.

A prime number is a positive integer possessing exactly two distinct positive divisors: 1 and itself. And a palindrome number reads the same backward or forward.

For example, if the input is 6, the smallest prime palindrome larger than 6 is 7 which is a prime number and also reads the same backward and forward.

Approach to the solution

The problem is solved by a straightforward brute force approach which checks each number to see if it's a prime and a palindrome.

To implement this, for each possible palindrome, we can check if it is larger than the given number, then we can verify if it is a prime one. As it is a brute force algorithm, it is expensive and the complexity is proportional to the number of possible palindrome numbers.

To reduce the number of potential palindrome numbers, we can calculate how many digits the given number has, and generate all larger palindrome numbers with an even number of digits.

Example

Let's try to understand this through an example.

Example: 8

Output: 11

Step 1: Calculate the number of digits. For 8, it is 1.

Step 2: As we want palindrome numbers larger than 8, we start generating two digits palindrome numbers. We start from 10 to 20 and verify if they are prime and palindrome. We found the number 11, which is prime and palindrome.

Step 3: So, our output is 11.

C++ Solution

Here is the solution in C++.

1
2cpp
3class Solution {
4public:
5 int primePalindrome(int n) {
6   if (n <= 2)
7     return 2;
8   if (n == 3)
9     return 3;
10   if (n <= 5)
11     return 5;
12   if (n <= 7)
13     return 7;
14   if (n <= 11)
15     return 11;
16
17   int nLength = to_string(n).length();
18
19   while (true) {
20     for (const int num : getPalindromes(nLength))
21       if (num >= n && isPrime(num))
22         return num;
23     ++nLength;
24   }
25   throw;
26 }
27
28private:
29 vector<int> getPalindromes(int n) {
30   vector<int> palindromes;
31   const int length = n / 2;
32   for (int i = pow(10, length - 1); i < pow(10, length); ++i) {
33     const string s = to_string(i);
34     string reversedS = s;
35     reverse(begin(reversedS), end(reversedS));
36     for (int j = 0; j < 10; ++j)
37       palindromes.push_back(stoi(s + to_string(j) + reversedS));
38   }     
39   return palindromes;
40 }
41
42 bool isPrime(int num) {
43   for (int i = 2; i < sqrt(num) + 1; ++i)  
44     if (num % i == 0)
45       return false;
46   return true;
47 }
48};

Python, Java, Javascript, and c# Solutions

Currently, I only have the C++ version of the solution. Converting this code into Python, Java, Javascript, and c# languages is necessary as per the requirement. However, the logic of the problem solution will remain exactly the same as explained in the example and approach.## Python Solution

Here is the equivalent Python solution for the problem.

1
2python
3import math
4
5class Solution:
6    def primePalindrome(self, N: int) -> int:
7        def is_prime(n):
8            if n < 2: return False
9            if n == 2 or n == 3: return True
10            if n%2 == 0 or n%3 == 0: return False
11            j = 5
12            while(j * j <= n):
13                if n%j == 0 or n%(j+2) == 0: return False
14                j += 6
15            return True
16
17        if N <= 2: return 2
18        if N == 3: return 3
19        if N <= 5: return 5
20        if N <= 7: return 7
21        if N <= 11: return 11
22        
23        length = len(str(N))
24
25        while True:
26            start = 10**(length // 2)
27            for i in range(start, 10*start):
28                s = str(i)
29                p = int(s + s[-1-(length%2 == 0):-1:-1])
30                if p >= N and is_prime(p): return p
31            length += 1

Java Solution

This solution can also be written in Java as follows:

1
2java
3class Solution {
4    public int primePalindrome(int N) {
5        if (N <= 2) return 2;
6        if (N == 3) return 3;
7        if (N <= 5) return 5;
8        if (N <= 7) return 7;
9        if (N <= 11) return 11;
10
11        int length = Integer.toString(N).length();
12        while (true) {
13            for (int num : getPalindromes(length)) {
14                if (num >= N && isPrime(num)) {
15                    return num;
16                }
17            }
18            length++;
19        }
20    }
21
22    private boolean isPrime(int num) {
23        for (int i = 2; i <= Math.sqrt(num); ++i)
24            if (num % i == 0)
25                return false;
26
27        return true;
28    }
29
30    private List<Integer> getPalindromes(int n) {
31        List<Integer> palindromes = new ArrayList<>();
32        int length = n / 2;
33
34        int start = (int) Math.pow(10, length - 1);
35        int end = (int) Math.pow(10, length);
36        
37        for (int i = start; i < end; ++i) {
38            String s = Integer.toString(i);
39            StringBuilder reversedS = new StringBuilder(s).reverse();
40            for (int j = 0; j < 10; ++j) {
41                int palindrome = Integer.parseInt(s + Integer.toString(j) + reversedS.toString());
42                palindromes.add(palindrome);
43            }
44        }
45
46        return palindromes;
47    }
48}

Javascript Solution

Finally, here is the solution in JavaScript:

1
2js
3class Solution {
4    primePalindrome(n) {
5        while(true){
6            if(this.isPalindrome(n) && this.isPrime(n)) return n;
7            n++;
8            if(10000000 < n && n < 100000000) n = 100000000;
9        }
10    };
11
12    isPalindrome(n) {
13        let s = n.toString();
14        return s === s.split("").reverse().join("");
15    };
16
17    isPrime(n) {
18        if(n < 2) return false;
19        let sqrt = Math.sqrt(n);
20        for(let i = 2; i <= sqrt; i++)
21            if(n % i === 0) return false;
22        return true;
23    };
24};
25
26let s = new Solution();
27console.log(s.primePalindrome(8));  // Outputs: 11