Prime Palindrome

Med

#0820Time: 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.

Patterns

Math Number Theory

Prompt

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 * 10⁸].

Example 1:

Input: n = 6
Output: 7

Example 2:

Input: n = 8
Output: 11

Example 3:

Input: n = 13
Output: 101

Constraints:

1 <= n <= 10⁸

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 num initialized to n.
In each iteration, check if num is a palindrome. A number is a palindrome if its string representation is the same as its reverse.
If num is a palindrome, check if it is a prime number. A number x is prime if it's greater than 1 and not divisible by any integer from 2 up to its square root.
If num is both a palindrome and a prime, it is our answer. Return num.
If not, increment num and continue the loop.
A small optimization can be added: all 8-digit palindromes are divisible by 11. So, if num reaches 10^7, we can skip directly to 10^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.

1class Solution {2    public int primePalindrome(int n) {3        while (true) {4            if (isPalindrome(n) && isPrime(n)) {5                return n;6            }7            n++;8            // All 8-digit palindromes are divisible by 11.9            // If n reaches 10,000,000, we can skip to 100,000,000.10            if (n > 10_000_000 && n < 100_000_000) {11                n = 100_000_000;12            }13        }14    }15 16    private boolean isPalindrome(int x) {17        if (x < 0 || (x != 0 && x % 10 == 0)) return false;18        int reversed = 0;19        int original = x;20        while (x > 0) {21            reversed = reversed * 10 + x % 10;22            x /= 10;23        }24        return original == reversed;25    }26 27    private boolean isPrime(int x) {28        if (x < 2) return false;29        if (x % 2 == 0) return x == 2;30        for (int i = 3; i * i <= x; i += 2) {31            if (x % i == 0) {32                return false;33            }34        }35        return true;36    }37}

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.

A more efficient approach is to generate only palindromic numbers and then test them for primality. This avoids checking every number between n and the answer. We can further optimize this by observing a mathematical property: all even-length palindromes, except for 11, are divisible by 11 and thus not prime. Therefore, we only need to generate and test odd-length palindromes.

Algorithm

Handle edge cases: If n is between 8 and 11, the answer is 11, the only even-length prime palindrome.
Iterate through possible roots k starting from 1. For an answer up to 2*10^8, the root will have at most 5 digits, so we can cap the loop for k at 20000.
For each root k, construct the corresponding odd-length palindrome p.
- Convert k to a string s.
- Create a reversed version of s, let's call it rev_s.
- The palindrome string is s concatenated with rev_s excluding its first character (e.g., root 123 -> s="123", rev_s="321", palindrome is "123" + "21" -> 12321).
- Convert this string back to an integer p.
Check if the generated palindrome p is greater than or equal to n.
If it is, check if p is prime.
If p is also prime, return p. Since we generate palindromes in increasing order, this will be the smallest one.

Walkthrough

This method focuses on the fact that palindromes are sparse. Instead of checking every number, we only generate candidates that are already palindromes. An odd-length palindrome is uniquely determined by its first half, which we call the 'root'. For example, the palindrome 12321 is formed from the root 123.

The algorithm iterates through roots k (1, 2, 3, ...), constructs the full odd-length palindrome from each root, and then checks two conditions: if the palindrome is greater than or equal to n, and if it's prime. Since the roots are processed in increasing order, the generated palindromes are also in increasing order. The first palindrome that satisfies both conditions is the smallest prime palindrome and is the correct answer.

1class Solution {2    public int primePalindrome(int n) {3        // Handle small cases and the only even-length prime palindrome4        if (n >= 8 && n <= 11) {5            return 11;6        }7 8        // Generate odd-length palindromes from their roots.9        // For n <= 10^8, the answer is <= 2*10^8.10        // A 9-digit palindrome has a 5-digit root.11        // A root of 20000 generates 200000002. So we can cap the root loop.12        for (int k = 1; k < 20000; k++) {13            String s = Integer.toString(k);14            String reversed_s = new StringBuilder(s).reverse().toString();15            int p = Integer.parseInt(s + reversed_s.substring(1));16 17            if (p >= n && isPrime(p)) {18                return p;19            }20        }21        22        // The problem guarantees an answer exists in the range [2, 2 * 10^8],23        // which is covered by the loop above. For example, the next prime24        // palindrome after 10^8 is 100300301, from root k=10030.25        return -1; // Should not be reached.26    }27 28    private boolean isPrime(int x) {29        if (x < 2 || x % 2 == 0) {30            return x == 2;31        }32        for (int i = 3; i * i <= x; i += 2) {33            if (x % i == 0) {34                return false;35            }36        }37        return true;38    }39}

Complexity

Time

O(K_ans * sqrt(P_ans)), where `P_ans` is the answer and `K_ans` is its root. Since `K_ans` is approximately `sqrt(P_ans)`, the complexity is roughly `O(P_ans)`. However, in practice, we only check a small number of palindromes starting from `n`, making it very fast.

Space

O(log K), where K is the root of the palindrome. This space is for storing the string representation of the root.

Trade-offs

Pros

Significantly more efficient as it drastically reduces the number of primality tests.
Leverages a mathematical property of palindromes to simplify the search space.

Cons

The logic for generating palindromes from a root is slightly more complex than a simple iteration.

Solutions

Solution

1class Solution {2public3  int primePalindrome(int n) {4    while (true) {5      if (reverse(n) == n && isPrime(n)) {6        return n;7      }8      if (n > 10000000 && n < 100000000) {9        n = 100000000;10      }11      ++n;12    }13  }14private15  boolean isPrime(int x) {16    if (x < 2) {17      return false;18    }19    for (int v = 2; v * v <= x; ++v) {20      if (x % v == 0) {21        return false;22      }23    }24    return true;25  }26private27  int reverse(int x) {28    int res = 0;29    while (x != 0) {30      res = res * 10 + x % 10;31      x /= 10;32    }33    return res;34  }35}

1class Solution {2public:3  int primePalindrome(int n) {4    while (1) {5      if (reverse(n) == n && isPrime(n))6        return n;7      if (n > 10000000 && n < 100000000)8        n = 100000000;9      ++n;10    }11  }12  bool isPrime(int x) {13    if (x < 2)14      return false;15    for (int v = 2; v * v <= x; ++v)16      if (x % v == 0)17        return false;18    return true;19  }20  int reverse(int x) {21    int res = 0;22    while (x) {23      res = res * 10 + x % 10;24      x /= 10;25    }26    return res;27  }28};

1class Solution:2    def primePalindrome(self, n: int) -> int: def is_prime(x): if x < 2: return False v = 2 while v * v <= x: if x % v == 0: return False v += 1 return True def reverse(x): res = 0 while x: res = res * 10 + x % 10 x //= 10 return res while 1: if reverse(n) == n and is_prime(n): return n if 10 ** 7 < n < 10 ** 8: n = 10 ** 8 n += 1

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.

← Previous

Previous problem

Next problem