LeetCode 866 - Prime Palindrome

This problem asks us to find the smallest number greater than or equal to n that satisfies two properties simultaneously: 1. The number must be a palindrome. 2. The number must be prime. A palindrome is a number that reads the same forward and backward.

leetcodemediummathnumber-theory

LeetCode Problem 866

Difficulty: 🟡 Medium
Topics: Math, Number Theory

Solution

Problem Understanding

This problem asks us to find the smallest number greater than or equal to n that satisfies two properties simultaneously:

  1. The number must be a palindrome.
  2. The number must be prime.

A palindrome is a number that reads the same forward and backward. For example, 121, 1331, and 7 are palindromes.

A prime number is a number greater than 1 that has exactly two divisors, 1 and itself. Examples include 2, 3, 5, 7, 11, and 13.

The input consists of a single integer n, and we must return the first number x such that:

  • x >= n
  • x is a palindrome
  • x is prime

The constraints tell us that:

  • 1 <= n <= 10^8
  • The answer is guaranteed to exist and will not exceed 2 * 10^8

At first glance, this might seem like a straightforward search problem where we increment from n upward and test every number. However, primality testing is relatively expensive, and there are many non-palindromic numbers. Since the upper bound can be as large as two hundred million, a naive brute-force solution would be far too slow.

There are also several important observations and edge cases:

  • Single-digit primes such as 2, 3, 5, and 7 are valid answers.
  • 11 is the only even-length palindrome that is prime.
  • Every other even-length palindrome is divisible by 11, which means it cannot be prime.
  • Large ranges without prime palindromes could cause a brute-force search to perform many unnecessary checks.
  • We need an efficient way to generate palindrome candidates instead of checking every integer.

These observations lead directly to the optimal solution.

Approaches

Brute Force Approach

The most direct approach is to start at n and increment upward one number at a time.

For every number:

  1. Check whether it is a palindrome.
  2. If it is, check whether it is prime.
  3. Return the first number satisfying both conditions.

This approach is correct because it examines numbers in increasing order and stops at the first valid prime palindrome.

However, it is inefficient for large values of n. Most numbers are not palindromes, so we waste substantial time checking irrelevant candidates. Additionally, primality testing for many numbers becomes expensive as the search range grows.

In the worst case, we may examine millions of integers before finding the answer.

Optimal Approach

The key observation is that almost all even-length palindromes are composite.

For example:

  • 1221
  • 3443
  • 9009

All even-length palindromes are divisible by 11. The only exception is 11 itself.

This means we only need to generate:

  • Single-digit palindromes
  • 11
  • Odd-length palindromes

Instead of checking every integer, we directly construct palindrome candidates.

We generate an odd-length palindrome by:

  1. Taking a number such as 123
  2. Mirroring all digits except the last
  3. Producing 12321

This dramatically reduces the search space.

For every generated palindrome:

  1. Check whether it is at least n
  2. Check whether it is prime
  3. Return the first valid answer

This approach is much faster because the number of palindromes is tiny compared to the number of integers in the same range.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(k × √k) O(1) Checks every integer from n upward
Optimal O(P × √P) O(1) Generates only odd-length palindromes

Here, k represents the size of the searched numeric range, while P represents the number of palindrome candidates generated.

Algorithm Walkthrough

  1. Handle small edge cases immediately.

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.

These values are small prime palindromes and are easier to handle directly. 2. Generate odd-length palindromes.

Start with an integer half = 1.

Convert half into a string. For example:

  • 1
  • 12
  • 123

Then mirror all characters except the last one.

Examples:

  • "1" → "1"
  • "12" → "121"
  • "123" → "12321"

This guarantees the palindrome has odd length. 3. Convert the generated palindrome back into an integer.

For example:

  • "12321" becomes 12321
  1. Skip palindromes smaller than n.

Since we need the smallest prime palindrome greater than or equal to n, smaller values are irrelevant. 5. Test whether the palindrome is prime.

Use trial division up to √x.

Important optimizations:

  • Reject even numbers immediately
  • Only test odd divisors
  • Stop once divisor squared exceeds the number
  1. Return the first palindrome that passes the primality test.

Because palindromes are generated in increasing order, the first valid one is guaranteed to be the smallest answer.

Why it works

The algorithm works because it systematically generates all odd-length palindromes in increasing order. Every prime palindrome greater than 11 must have odd length, since every even-length palindrome is divisible by 11. Therefore, the search never misses a valid answer. Since candidates are processed in ascending order, the first prime palindrome found is guaranteed to be the smallest valid answer.

Python Solution

class Solution:
    def primePalindrome(self, n: int) -> int:
        def is_prime(num: int) -> bool:
            if num < 2:
                return False
            
            if num % 2 == 0:
                return num == 2
            
            divisor = 3
            
            while divisor * divisor <= num:
                if num % divisor == 0:
                    return False
                divisor += 2
            
            return True

        # Handle small prime palindromes directly
        small_answers = [2, 3, 5, 7, 11]
        
        for value in small_answers:
            if n <= value:
                return value

        half = 1

        while True:
            s = str(half)

            # Generate odd-length palindrome
            palindrome = int(s + s[-2::-1])

            if palindrome >= n and is_prime(palindrome):
                return palindrome

            half += 1

The implementation begins with the is_prime helper function. This function performs efficient primality testing using trial division. Even numbers are handled separately because any even number greater than 2 is not prime.

The main function first handles small known prime palindromes directly. This avoids complications involving even-length palindromes and simplifies the later logic.

The variable half is used to construct palindromes. For each value:

  • Convert it to a string
  • Mirror all digits except the final digit
  • Form an odd-length palindrome

For example:

  • 123 becomes 12321

The palindrome is then checked against n. If it is large enough and prime, it is immediately returned.

Since palindromes are generated in increasing order, the first valid answer is correct.

Go Solution

package main

func primePalindrome(n int) int {
	isPrime := func(num int) bool {
		if num < 2 {
			return false
		}

		if num%2 == 0 {
			return num == 2
		}

		for divisor := 3; divisor*divisor <= num; divisor += 2 {
			if num%divisor == 0 {
				return false
			}
		}

		return true
	}

	smallAnswers := []int{2, 3, 5, 7, 11}

	for _, value := range smallAnswers {
		if n <= value {
			return value
		}
	}

	for half := 1; ; half++ {
		palindrome := buildPalindrome(half)

		if palindrome >= n && isPrime(palindrome) {
			return palindrome
		}
	}
}

func buildPalindrome(half int) int {
	result := half
	half /= 10

	for half > 0 {
		result = result*10 + half%10
		half /= 10
	}

	return result
}

The Go implementation follows the same overall strategy as the Python version, but there are some language-specific differences.

Instead of using string manipulation to build palindromes, the Go version constructs them mathematically. This avoids repeated string allocations and is slightly more efficient.

The helper function buildPalindrome appends reversed digits to the original number while skipping the final digit to ensure odd length.

Go also requires explicit slice creation for the small prime palindrome values and uses a closure for the primality test.

Since all calculations remain comfortably within 32-bit integer limits for this problem, integer overflow is not a concern.

Worked Examples

Example 1

Input:

n = 6

The algorithm first checks small prime palindromes.

Candidate Condition
2 too small
3 too small
5 too small
7 valid

The answer is:

7

Example 2

Input:

n = 8

Small prime palindrome checks:

Candidate Condition
2 too small
3 too small
5 too small
7 too small
11 valid

The answer is:

11

Example 3

Input:

n = 13

Small prime palindromes are all too small.

Now we generate odd-length palindromes.

half Generated Palindrome Prime?
1 1 no
2 2 yes but too small
3 3 yes but too small
4 4 no
5 5 yes but too small
6 6 no
7 7 yes but too small
8 8 no
9 9 no
10 101 yes

The answer is:

101

Complexity Analysis

Measure Complexity Explanation
Time O(P × √P) Each palindrome candidate may require primality testing
Space O(1) Only a few variables are used

The dominant cost comes from primality testing. For each generated palindrome, we may test divisibility up to its square root. However, because the number of palindromes is dramatically smaller than the number of integers in the range, the algorithm performs efficiently in practice.

The space complexity remains constant because we do not store large auxiliary data structures.

Test Cases

sol = Solution()

assert sol.primePalindrome(1) == 2      # smallest possible input
assert sol.primePalindrome(2) == 2      # already a prime palindrome
assert sol.primePalindrome(6) == 7      # example case
assert sol.primePalindrome(8) == 11     # example case
assert sol.primePalindrome(13) == 101   # skips non-prime palindromes
assert sol.primePalindrome(11) == 11    # only even-length prime palindrome
assert sol.primePalindrome(12) == 101   # must skip all even-length palindromes
assert sol.primePalindrome(31) == 101   # next valid prime palindrome
assert sol.primePalindrome(100) == 101  # nearby palindrome
assert sol.primePalindrome(9989900) == 100030001  # large input stress case

Test Summary

Test Why
n = 1 Validates smallest boundary
n = 2 Checks direct prime palindrome
n = 6 Basic example
n = 8 Validates 11 handling
n = 13 Ensures palindrome generation works
n = 11 Tests special even-length case
n = 12 Confirms even-length palindromes are skipped
n = 31 Tests larger jump to next solution
n = 100 Verifies nearby prime palindrome
n = 9989900 Stress test for large values

Edge Cases

One important edge case is when n is less than or equal to 11. The value 11 is special because it is the only even-length palindrome that is prime. A solution that blindly skips all even-length palindromes would incorrectly fail for inputs like 8 or 11. The implementation handles this explicitly by returning small known prime palindromes directly.

Another critical edge case involves large ranges without nearby prime palindromes. For example, after 13, the next answer is 101. A brute-force solution wastes time checking every intermediate number. The optimized implementation avoids this issue entirely by generating only palindrome candidates.

A third subtle edge case is the primality check itself. Many incorrect implementations test divisibility all the way up to n - 1, which is unnecessarily slow. Others forget to handle even numbers separately. The provided solution correctly checks divisibility only up to the square root of the number and skips even divisors, making the check both correct and efficient.