Skip to main content
Talentd

Prime Palindrome - Solution & Explanation

MediumMathNumber Theory12 min readAsked at: Amazon, Meta, Google
Practice this problem

Problem Statement

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

Approach Overview

Problem 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.

Approach 1: Brute Force Approach

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.

Code

PythonC++JavaC#JavaScript

Python

C++

Java

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Optimized Approach with Skip for Non-Palindrome Primes

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.

Code

PythonC++JavaC#JavaScript

Python

C++

Java

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space complexity: O(1), as no additional data structures are used.

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.
Space complexity: O(1) on storage structures for checks.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SearchO(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

Video Solution

Prime Palindrome | Leetcode #866 • Techdose • 3,561 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Prime Palindrome easy or hard?
Prime Palindrome is typically considered a medium-level problem. The brute force idea is simple, but the optimized solution requires recognizing that even-length palindromes greater than 11 cannot be prime and generating palindrome candidates efficiently.
How to solve Prime Palindrome efficiently?
Generate palindromes instead of checking every integer. Build odd-length palindromes by mirroring the first half of the number, then run a primality test using trial division up to sqrt(x). Skip even-length palindromes larger than 11 because they are always divisible by 11.
What is the best approach for Prime Palindrome?
The most efficient approach generates palindrome numbers directly and then checks if they are prime. Instead of scanning every integer, you construct palindromes by mirroring digits and run a primality test on each candidate. Skipping even-length palindromes (except 11) further reduces the search space.
Is Prime Palindrome asked at Google/Amazon/Meta?
Prime Palindrome represents the type of number theory and math-heavy question sometimes seen in interviews at companies like Google or Amazon. It tests knowledge of palindrome construction, prime testing, and optimization through mathematical observations.
What data structure is used in Prime Palindrome?
The problem mainly relies on mathematical operations rather than complex data structures. String manipulation or integer digit operations are used to construct and check palindromes, while a simple loop performs the primality test.
What is the time complexity of Prime Palindrome?
The brute force method runs in roughly O(k * sqrt(n)) because each candidate number requires a primality test up to sqrt(n). The optimized approach generates only palindrome candidates and checks primality, giving an effective complexity around O(P * sqrt(P)), where P is the candidate palindrome size.
Prime Palindrome Python or Java solution approach?
Most Python or Java solutions generate palindrome candidates and then verify primality with a sqrt-based check. This avoids iterating through every integer and significantly improves performance compared with brute force scanning.

Ready to solve this problem?

Practice Prime Palindrome with our built-in code editor and test cases.

Practice on FleetCode
Previous

Sum of k-Mirror Numbers