Problem Description

The "Prime Palindrome" problem asks you to find the smallest integer x that is both a palindrome and a prime number, and is greater than or equal to a given integer n.

• Palindrome: An integer that reads the same backward as forward (e.g., 121, 1331).
• Prime: An integer greater than 1 with no divisors other than 1 and itself.

Constraints:

• You must return the first such number found, i.e., the smallest x >= n that satisfies both conditions.
• You do not need to consider numbers with more than 8 digits (the answer is always less than 2 * 10⁸).

Thought Process

At first glance, a brute-force approach suggests checking every number starting from n to see if it is both a palindrome and a prime. However, this is not efficient, especially for large values of n.

To optimize, we realize:

• There are far fewer palindromic numbers than general numbers, so it's better to generate palindromes and check if they are prime.
• Checking if a number is a palindrome is easy (convert to string, check if reversed is the same).
• Checking for primality is more expensive, so we want to minimize these checks.
• All even-length palindromes (except 11) are divisible by 11, so we can skip generating them for numbers greater than 11.

Solution Approach

Here is the step-by-step approach:

1. Generate palindromes in increasing order:
   • For each possible length of palindrome (starting from the length of n), generate all palindromic numbers.
   • For odd-length palindromes, construct by mirroring the first half (and optionally a middle digit).
   • For even-length palindromes, except 11, we can skip these as they are rarely prime.
2. For each palindrome, check if it is prime:
   • For a given palindrome, check divisibility by all integers up to its square root.
   • Skip even numbers and known small divisors for efficiency.
3. Return the first palindrome that is prime and at least n.

Why this works: By generating palindromes directly and checking for primality, we avoid unnecessary checks and leverage the rarity of prime palindromes to our advantage.

Example Walkthrough

Suppose n = 31.

1. Generate palindromes ≥ 31: 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, 131, ...
2. Check each for primality:
   • 33: Not prime (divisible by 3).
   • 44: Not prime (divisible by 2).
   • 55: Not prime (divisible by 5).
   • 66: Not prime (divisible by 2).
   • 77: Not prime (divisible by 7).
   • 88: Not prime (divisible by 2).
   • 99: Not prime (divisible by 3).
   • 101: Prime!
3. Return 101 as the answer.

Time and Space Complexity

Brute-force approach:

• Time: O(M log M), where M is the upper bound, since for each number we check palindrome and primality.
• Space: O(1), only storing current number and checks.

• Time: O(K * sqrt(N)), where K is the number of palindromic numbers generated (much less than N), and each prime check is up to sqrt(N).
• Space: O(1), as we generate palindromes and check them on the fly.

The optimization comes from checking far fewer numbers for primality.

Summary

To solve the Prime Palindrome problem efficiently, we generate palindromic numbers in increasing order starting from n, and check each for primality. By skipping even-length palindromes (except 11) and leveraging the rarity of prime palindromes, we dramatically reduce the search space, making the solution both elegant and efficient.

Code Implementation

class Solution:
    def primePalindrome(self, n: int) -> int:
        def is_prime(x):
            if x < 2: return False
            if x == 2: return True
            if x % 2 == 0: return False
            r = int(x ** 0.5) + 1
            for d in range(3, r, 2):
                if x % d == 0:
                    return False
            return True

        # Single digit palindromes
        for x in range(n, 12):
            if is_prime(x):
                return x

        # Generate odd length palindromes
        for length in range(1, 6):  # 10^5 covers up to 10^8
            start = 10**(length-1)
            end = 10**length
            for root in range(start, end):
                s = str(root)
                pal = int(s + s[-2::-1])  # Odd length palindrome
                if pal >= n and is_prime(pal):
                    return pal
        return -1
      

class Solution {
public:
    bool isPrime(int x) {
        if (x < 2) return false;
        if (x == 2) return true;
        if (x % 2 == 0) return false;
        for (int d = 3; d * d <= x; d += 2)
            if (x % d == 0) return false;
        return true;
    }
    int primePalindrome(int n) {
        for (int x = n; x < 12; ++x)
            if (isPrime(x)) return x;

        for (int len = 1; len <= 5; ++len) {
            int start = pow(10, len - 1), end = pow(10, len);
            for (int root = start; root < end; ++root) {
                string s = to_string(root);
                string rev = s.substr(0, s.size() - 1);
                reverse(rev.begin(), rev.end());
                string palStr = s + rev;
                int pal = stoi(palStr);
                if (pal >= n && isPrime(pal))
                    return pal;
            }
        }
        return -1;
    }
};
      

class Solution {
    public int primePalindrome(int n) {
        for (int x = n; x < 12; ++x)
            if (isPrime(x)) return x;

        for (int len = 1; len <= 5; ++len) {
            int start = (int)Math.pow(10, len - 1), end = (int)Math.pow(10, len);
            for (int root = start; root < end; ++root) {
                String s = Integer.toString(root);
                StringBuilder rev = new StringBuilder(s.substring(0, s.length() - 1)).reverse();
                String palStr = s + rev.toString();
                int pal = Integer.parseInt(palStr);
                if (pal >= n && isPrime(pal))
                    return pal;
            }
        }
        return -1;
    }

    private boolean isPrime(int x) {
        if (x < 2) return false;
        if (x == 2) return true;
        if (x % 2 == 0) return false;
        for (int d = 3; d * d <= x; d += 2)
            if (x % d == 0) return false;
        return true;
    }
}
      

var primePalindrome = function(n) {
    function isPrime(x) {
        if (x < 2) return false;
        if (x === 2) return true;
        if (x % 2 === 0) return false;
        for (let d = 3; d * d <= x; d += 2)
            if (x % d === 0) return false;
        return true;
    }

    for (let x = n; x < 12; ++x)
        if (isPrime(x)) return x;

    for (let len = 1; len <= 5; ++len) {
        let start = Math.pow(10, len - 1), end = Math.pow(10, len);
        for (let root = start; root < end; ++root) {
            let s = root.toString();
            let rev = s.slice(0, s.length - 1).split('').reverse().join('');
            let pal = parseInt(s + rev);
            if (pal >= n && isPrime(pal))
                return pal;
        }
    }
    return -1;
};