Prime Palindrome
MedPrompt
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, and13are 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,
101and12321are 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: 7Example 2:
Input: n = 8
Output: 11Example 3:
Input: n = 13
Output: 101
Constraints:
1 <= n <= 108
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves iterating through integers starting from n. For each integer, we perform two checks: first, whether it's a palindrome, and second, whether it's a prime number. The first integer that satisfies both conditions is the smallest prime palindrome greater than or equal to n and is returned.
Algorithm
- Start a loop with a variable
numinitialized ton. - In each iteration, check if
numis a palindrome. A number is a palindrome if its string representation is the same as its reverse. - If
numis a palindrome, check if it is a prime number. A numberxis prime if it's greater than 1 and not divisible by any integer from 2 up to its square root. - If
numis both a palindrome and a prime, it is our answer. Returnnum. - If not, increment
numand continue the loop. - A small optimization can be added: all 8-digit palindromes are divisible by 11. So, if
numreaches10^7, we can skip directly to10^8.
Walkthrough
The algorithm begins by checking every integer num starting from the input n. For each num, it first verifies if it's a palindrome. This can be done by converting the number to a string and comparing it with its reverse. If the number is a palindrome, the algorithm proceeds to check if it's also a prime number. The primality test involves checking for divisibility from 2 up to the square root of the number. The loop continues, incrementing num by one at each step, until a number is found that is both a palindrome and a prime. This number is then the desired result.
class Solution { public int primePalindrome(int n) { while (true) { if (isPalindrome(n) && isPrime(n)) { return n; } n++; // All 8-digit palindromes are divisible by 11. // If n reaches 10,000,000, we can skip to 100,000,000. if (n > 10_000_000 && n < 100_000_000) { n = 100_000_000; } } } private boolean isPalindrome(int x) { if (x < 0 || (x != 0 && x % 10 == 0)) return false; int reversed = 0; int original = x; while (x > 0) { reversed = reversed * 10 + x % 10; x /= 10; } return original == reversed; } private boolean isPrime(int x) { if (x < 2) return false; if (x % 2 == 0) return x == 2; for (int i = 3; i * i <= x; i += 2) { if (x % i == 0) { return false; } } return true; }}Complexity
Time
O(D * sqrt(M)), where M is the resulting prime palindrome and D is the difference `M - n`. In the worst case, the gap D can be very large, making this approach too slow.
Space
O(log M), where M is the resulting prime palindrome. This space is used to store the number as a string for the palindrome check.
Trade-offs
Pros
Simple to understand and implement.
Cons
Highly inefficient and will likely result in a "Time Limit Exceeded" error for larger inputs.
Performs a costly primality test on many numbers that are not palindromes.
Solutions
Solution
class Solution {public int primePalindrome(int n) { while (true) { if (reverse(n) == n && isPrime(n)) { return n; } if (n > 10000000 && n < 100000000) { n = 100000000; } ++n; } }private boolean isPrime(int x) { if (x < 2) { return false; } for (int v = 2; v * v <= x; ++v) { if (x % v == 0) { return false; } } return true; }private int reverse(int x) { int res = 0; while (x != 0) { res = res * 10 + x % 10; x /= 10; } return res; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.