Prime Palindrome

MEDIUM

Description

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

Checkout 2 different approaches to solve Prime Palindrome. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

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.

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.

class Solution {
    public int primePalindrome(int n) {
        while (true) {
            if (isPalindrome(n) && isPrime(n)) {
                return n;
            }
            n++;
            // All 8-digit palindromes are divisible by 11.
            // If n reaches 10,000,000, we can skip to 100,000,000.
            if (n > 10_000_000 && n < 100_000_000) {
                n = 100_000_000;
            }
        }
    }

    private boolean isPalindrome(int x) {
        if (x < 0 || (x != 0 && x % 10 == 0)) return false;
        int reversed = 0;
        int original = x;
        while (x > 0) {
            reversed = reversed * 10 + x % 10;
            x /= 10;
        }
        return original == reversed;
    }

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

Complexity Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Prime Palindrome. Click on different languages to view the code.

class Solution {
public
  int primePalindrome(int n) {
    while (true) {
      if (reverse(n) == n && isPrime(n)) {
        return n;
      }
      if (n > 10000000 && n < 100000000) {
        n = 100000000;
      }
      ++n;
    }
  }
private
  boolean isPrime(int x) {
    if (x < 2) {
      return false;
    }
    for (int v = 2; v * v <= x; ++v) {
      if (x % v == 0) {
        return false;
      }
    }
    return true;
  }
private
  int reverse(int x) {
    int res = 0;
    while (x != 0) {
      res = res * 10 + x % 10;
      x /= 10;
    }
    return res;
  }
}

Video Solution

Watch the video walkthrough for Prime Palindrome

Patterns:

MathNumber Theory