In this guide, you will get 866. Prime Palindrome LeetCode Solution with the best time and space complexity. The solution to Prime Palindrome problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 <= 108
Complexity Analysis
Time Complexity:
Space Complexity:
866. Prime Palindrome LeetCode Solution in C++
class Solution {
public:
int primePalindrome(int n) {
if (n <= 2)
return 2;
if (n == 3)
return 3;
if (n <= 5)
return 5;
if (n <= 7)
return 7;
if (n <= 11)
return 11;
int nLength = to_string(n).length();
while (true) {
for (const int num : getPalindromes(nLength))
if (num >= n && isPrime(num))
return num;
++nLength;
}
throw;
}
private:
vector<int> getPalindromes(int n) {
vector<int> palindromes;
const int length = n / 2;
for (int i = pow(10, length - 1); i < pow(10, length); ++i) {
const string s = to_string(i);
string reversedS = s;
ranges::reverse(reversedS);
for (int j = 0; j < 10; ++j)
palindromes.push_back(stoi(s + to_string(j) + reversedS));
}
return palindromes;
}
bool isPrime(int num) {
for (int i = 2; i < sqrt(num) + 1; ++i)
if (num % i == 0)
return false;
return true;
}
}; /* code provided by PROGIEZ */
866. Prime Palindrome LeetCode Solution in Java
class Solution {
public int primePalindrome(int n) {
if (n <= 2)
return 2;
if (n == 3)
return 3;
if (n <= 5)
return 5;
if (n <= 7)
return 7;
if (n <= 11)
return 11;
int nLength = String.valueOf(n).length();
while (true) {
for (final int num : getPalindromes(nLength))
if (num >= n && isPrime(num))
return num;
++nLength;
}
}
private List<Integer> getPalindromes(int n) {
List<Integer> palindromes = new ArrayList<>();
int length = n / 2;
for (int i = (int) Math.pow(10, length - 1); i < (int) Math.pow(10, length); ++i) {
String s = String.valueOf(i);
String reversedS = new StringBuilder(s).reverse().toString();
for (int j = 0; j < 10; ++j)
palindromes.add(Integer.valueOf(s + String.valueOf(j) + reversedS));
}
return palindromes;
}
private boolean isPrime(int num) {
for (int i = 2; i < (int) Math.sqrt(num) + 1; ++i)
if (num % i == 0)
return false;
return true;
}
} // code provided by PROGIEZ
866. Prime Palindrome LeetCode Solution in Python
class Solution:
def primePalindrome(self, n: int) -> int:
def getPalindromes(n: int) -> int:
length = n // 2
for i in range(10**(length - 1), 10**length):
s = str(i)
for j in range(10):
yield int(s + str(j) + s[::-1])
def isPrime(num: int) -> bool:
return not any(num % i == 0 for i in range(2, int(num**0.5 + 1)))
if n <= 2:
return 2
if n == 3:
return 3
if n <= 5:
return 5
if n <= 7:
return 7
if n <= 11:
return 11
nLength = len(str(n))
while True:
for num in getPalindromes(nLength):
if num >= n and isPrime(num):
return num
nLength += 1 # code by PROGIEZ
