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.
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.
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 <= 108Problem Overview: Given an integer n, return the smallest number greater than or equal to n that is both a palindrome and a prime. A palindrome reads the same forward and backward, while a prime number has exactly two divisors: 1 and itself.
Approach 1: Brute Force Search (Time: O(k * sqrt(n)), Space: O(1))
Start at n and iterate upward one number at a time. For every number, first check if it is a palindrome by converting it to a string and comparing it with its reverse, or by using two pointers from both ends. If the number is a palindrome, run a primality test by checking divisibility from 2 to sqrt(x). The first number that satisfies both conditions is the answer.
This method is straightforward and mirrors the problem definition. However, most integers are neither palindromes nor primes, so the algorithm wastes time checking many candidates. As n grows, the density of primes decreases and brute-force iteration becomes slow.
Approach 2: Optimized Palindrome Generation + Prime Check (Time: ~O(P * sqrt(P)), Space: O(1))
Instead of checking every number, generate only palindrome candidates. Construct palindromes by building the first half of the number and mirroring it to form the second half. This drastically reduces the search space because you skip all non-palindrome integers entirely.
A key observation from math and number theory: every even-length palindrome greater than 11 is divisible by 11, so it cannot be prime. The optimized approach therefore generates only odd-length palindromes (except the special case 11). For each generated palindrome, run a standard primality test using trial division up to sqrt(x). As soon as you find one that is both ≥ n and prime, return it.
This approach reduces the candidate space by orders of magnitude. Instead of scanning every integer, you jump directly between palindrome numbers and only perform primality checks on those candidates.
Recommended for interviews: The optimized palindrome-generation approach is what interviewers typically expect. Brute force demonstrates that you understand palindrome detection and primality testing, but generating palindromes directly shows stronger problem-solving ability and knowledge of number properties.
The brute force approach involves incrementing from the given number n until we find a number that is both a palindrome and a prime. This approach checks every number to see if it is a palindrome and, if it is, checks if it is a prime number.
This is not the most efficient solution since it checks every number in succession, but it is straightforward and easy to implement.
The smallest_prime_palindrome function starts at n and increases until it finds a number that is both a palindrome and a prime. is_palindrome checks if the number is a palindrome by converting it to a string and comparing it to its reverse. is_prime uses trial division to determine if a number is prime. This includes checks for small prime divisors to enhance efficiency.
Python
C++
Java
C#
JavaScript
Time complexity: Generally O(n * sqrt(n)), because for each number until the next prime palindrome, we may need to check its primality which takes sqrt(n) time.
Space complexity: O(1), as no additional data structures are used.
This approach skips checking numbers that cannot be palindromes. Recognizing that a number with an even number of digits cannot be a prime palindrome (except for 11), we avoid such unnecessary palindrome checks.
Also, leveraging specific palindrome generation techniques, such as half-length mirroring, enhances the efficiency instead of linearly checking each number for palindrome property.
This solution focuses on generating palindromes rather than checking every number. The generate_palindrome function creates palindromes based on mirrored half-values for both odd and even centered structures. For each potential palindrome, the primality is validated.
Python
C++
Java
C#
JavaScript
Time complexity: Improved to O(nlogn) for palindromes and O(sqrt(n)) for specific number primes, significantly reducing checked numbers.
Space complexity: O(1) on storage structures for checks.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time complexity: Generally O(n * sqrt(n)), because for each number until the next prime palindrome, we may need to check its primality which takes sqrt(n) time. |
| Optimized Approach with Skip for Non-Palindrome Primes | Time complexity: Improved to O(nlogn) for palindromes and O(sqrt(n)) for specific number primes, significantly reducing checked numbers. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Search | O(k * sqrt(n)) | O(1) | Good for understanding the problem or when n is small |
| Generate Palindromes + Prime Check | ~O(P * sqrt(P)) | O(1) | Preferred for interviews and large inputs since it skips non-palindrome numbers |
Prime Palindrome | Leetcode #866 • Techdose • 3,408 views views
Watch 8 more video solutions →Practice Prime Palindrome with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor