LeetCode 866: Prime Palindrome

Problem Restatement

We are given an integer n.

We need to return the smallest integer greater than or equal to n that is both:

1. Prime
2. A palindrome

A prime number has exactly two divisors:

1 and itself

A palindrome reads the same from left to right and right to left.

For example:

101
131
929

The answer is guaranteed to exist in the range:

[2, 2 * 10^8]

Input and Output

Function shape:

class Solution:
    def primePalindrome(self, n: int) -> int:
        ...

Examples

Example 1:

n = 6

The numbers greater than or equal to 6 are:

6, 7, 8, 9, 10, 11, ...

The first prime palindrome is:

7

So the answer is:

7

Example 2:

n = 8

The next prime palindrome is:

11

So the answer is:

11

Example 3:

n = 13

The next prime palindrome is:

101

So the answer is:

101

First Thought: Check Every Number

A direct solution is:

1. Start from n.
2. Check whether the number is a palindrome.
3. Check whether it is prime.
4. Return the first number that passes both tests.

This is simple, but it may scan too many numbers.

For example, starting near a large value could require checking many non-palindromes. Most numbers are not palindromes, so we should generate palindromes directly.

Key Insight

All even-length palindromes are divisible by 11.

For example:

1221 = 11 * 111
9009 = 11 * 819

So an even-length palindrome greater than 11 cannot be prime.

That means after handling small answers, we only need to generate odd-length palindromes.

An odd-length palindrome can be built from a prefix.

For example, prefix 123 creates:

12321

We use the prefix as the left half and mirror all but its last digit.

prefix = "123"
palindrome = "123" + "21"

This generates palindromes in increasing order as the prefix increases.

Algorithm

Handle small cases first:

2, 3, 5, 7, 11

Then generate odd-length palindromes.

For each prefix:

1. Convert the prefix to a string.
2. Mirror it without the last digit.
3. Convert the result back to an integer.
4. If the palindrome is at least n and prime, return it.

Since the answer is at most 2 * 10^8, it is enough to generate prefixes up to 100000.

That creates palindromes up to:

10000000001

which is far beyond the guaranteed answer range.

Correctness

Every returned number is a palindrome because it is constructed by mirroring a prefix.

The algorithm tests primality before returning, so every returned number is prime.

The small cases cover all one-digit prime palindromes and the only even-length prime palindrome, 11.

For all larger answers, any prime palindrome must have odd length because every even-length palindrome greater than 11 is divisible by 11.

The algorithm generates odd-length palindromes in increasing order of their prefix, which also gives increasing palindrome values.

Therefore, the first generated palindrome that is at least n and prime is the smallest valid prime palindrome greater than or equal to n.

Complexity

Let P be the number of generated palindrome candidates before the answer.

Here, A is the returned answer.

In practice, this is fast because we generate only palindromes, and only odd-length palindromes after the small cases.

Implementation

class Solution:
    def primePalindrome(self, n: int) -> int:
        def is_prime(x: int) -> bool:
            if x < 2:
                return False

            if x % 2 == 0:
                return x == 2

            divisor = 3
            while divisor * divisor <= x:
                if x % divisor == 0:
                    return False
                divisor += 2

            return True

        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

        for prefix in range(1, 100000):
            left = str(prefix)
            candidate = int(left + left[-2::-1])

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

        return -1

Code Explanation

The helper function checks primality:

def is_prime(x: int) -> bool:

Numbers below 2 are not prime:

if x < 2:
    return False

Even numbers are prime only when the number is exactly 2:

if x % 2 == 0:
    return x == 2

Then we test odd divisors only:

divisor = 3
while divisor * divisor <= x:

If any divisor is found, the number is not prime:

if x % divisor == 0:
    return False

The small prime palindromes are handled first:

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

This also handles 11, the only even-length prime palindrome.

Then we generate odd-length palindromes:

for prefix in range(1, 100000):

For each prefix:

left = str(prefix)
candidate = int(left + left[-2::-1])

The expression:

left[-2::-1]

reverses the prefix except for its last digit.

For example:

left = "123"
left[-2::-1] = "21"
candidate = 12321

If the candidate is large enough and prime:

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

we return it immediately.

Testing

def test_prime_palindrome():
    s = Solution()

    assert s.primePalindrome(1) == 2
    assert s.primePalindrome(2) == 2
    assert s.primePalindrome(6) == 7
    assert s.primePalindrome(8) == 11
    assert s.primePalindrome(13) == 101
    assert s.primePalindrome(100) == 101
    assert s.primePalindrome(9989900) == 100030001

    print("all tests passed")

test_prime_palindrome()

Test meaning: