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
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.