Prime Palindrome - Leetcode Solution

Problem Statement:

Given an integer n, return the smallest prime palindrome greater than or equal to n.

Recall that a number is prime if it's only divisors are 1 and itself, and it is greater than 1.

For example, 2,3,5,7,11 and 131 are prime numbers.

A number is a palindrome if it reads the same from left to right as it does from right to left. For example, 121 and 1331 are palindromes.

Solution:

The approach to solve this problem is to start from the given number n, and keep incrementing it until we find the smallest prime palindrome greater than or equal to n.

Let's start with a helper function to check if a number is a prime number or not.

Code:

bool isPrime(int n) {
    if (n <= 1) return false; // corner case
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

This function takes an integer n, and returns true if it's a prime number, false otherwise. The function first checks if n is less than or equal to 1, which is not a prime number. Then, it loops through all the numbers from 2 to square root of n, and checks if n is divisible by any of those numbers. If n is divisible by any number, it means it's not a prime number and we return false. Otherwise, we return true.

Now, we can start iterating from n and check if each number is a palindrome and a prime number.

Code:

int primePalindrome(int n) {
    while (true) {
        if (n == reverse(n) && isPrime(n)) return n; // check if n is palindrome and prime
        n++; // increment n
        if (n > 10 && n == reverse(n)) n = nextPalindrome(n); // check if n is a palindrome with even digits and increment to next palindrome
    }
}

We start by checking if n is a palindrome and a prime number using reverse() and isPrime() functions respectively. If n satisfies both conditions, we return n. If not, we increment n and continue checking until we find a palindrome prime number.

There is a corner case when n is a palindrome with even digits. In this case, we increment n to the next palindrome with odd digits, because no even-digit palindromes are prime except 11. We handle this case using the nextPalindrome() function.

Code:

int nextPalindrome(int n) {
    string str = to_string(n);
    int len = str.length();
    string nextStr = to_string(pow(10, len) + 1); // create string with 1 followed by len 0s and 1
    return stoi(nextStr);
}

This function takes an even-digit number n as input, and returns the next palindrome with odd digits. We convert n to a string and get its length. We then create a string with a 1 followed by len 0s and 1. For example, if n is 1234, we create a string 10001. We then convert this string back to an integer and return it.

The complete code for this problem is:

class Solution {
public:
    int primePalindrome(int n) {
        while (true) {
            if (n == reverse(n) && isPrime(n)) return n; // check if n is palindrome and prime
            n++; // increment n
            if (n > 10 && n == reverse(n)) n = nextPalindrome(n); // check if n is a palindrome with even digits and increment to next palindrome
        }
    }
    
    bool isPrime(int n) {
        if (n <= 1) return false; // corner case
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
    
    int reverse(int n) {
        int rev = 0;
        while (n > 0) {
            rev = (rev * 10) + (n % 10);
            n /= 10;
        }
        return rev;
    }
    
    int nextPalindrome(int n) {
        string str = to_string(n);
        int len = str.length();
        string nextStr = to_string(pow(10, len) + 1); // create string with 1 followed by len 0s and 1
        return stoi(nextStr);
    }
};

1