Prime Palindrome LeetCode Solution

Difficulty Level MediumViews 2362

Problem Statement

Prime Palindrome LeetCode Solution – We are given an integer and are asked to return the smallest prime palindrome greater or equal to the given integer ‘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.

The test cases are generated so that the answer always exists and is in the range [2, 2*10^8].

Examples & Explanations

Example 1:

Input: n = 6
Output: 7
Explanation: 7 is prime & palindrome

Example 2:

Input: n = 8
Output: 11
Explanation: 9 is palindrome but not prime, 10 is neither prime nor palindrome, hence 11

Example 3:

Input: n = 13
Output: 101
Explanation: no two digits number can be palindrome with both different digits, eg. palindromes having 2 digits are 22, 33, 44, 55 ..... but none of these are prime.

Approach

Brute-Force with optimization

We can iterate through all the numbers from n+1 to 2*10^8 (because it is given in the question that answers always exist and are in the range [2, 2*10^8]).

However, this approach will cause TLE. To optimize this solution we will use the fact that the smallest prime palindrome in the range [1e7, 1e8] is 100030001. Therefore, if n lies in this range simply start traversing from this number and keep checking every number if it is a prime and palindrome.

To further decrease the time complexity we can skip all the even numbers as they can never be prime. Hence, increment the pointer in the loop by 2 times at each iteration.

We can use 2 separate functions to check primality and if the number is a palindrome. Checking primality is an easy task but note that we defined the reverse function used in palindrome checking. This function divides the number by 10 every time in iteration and stores the remainder.

NOTE: we have not used the to_string inbuilt function to check the palindromic property. Using to_String takes a lot of time and will result in TLE.

Code

C++ code for Prime Palindrome LeetCode Solution

class Solution {
    bool isPrime(int n) {
        for(int i=2; i<=sqrt(n);i++) {
            if(n%i==0) return 0;
        }
        return 1;
    }

    int reverse(int n){
        int m = 0;
        while (n) {
            m = m*10 + n % 10;
            n /= 10;
        }
        return m;
    }
    
    int isPalindrome(int n){
        return n == reverse(n);
    }
public:
    int primePalindrome(int n) {
        if( n <= 2) return 2;
        
        if(n>=1e7 && n<=1e8) {
            n=100030001;
        }
        
        if(n%2==0) n++;
        
        for(int i=n; i>=n; i+=2){
            if(isPalindrome(i)) {
                if(isPrime(i)) return i;
            } 
        }
        return -1;
    }
};

Java code for Prime Palindrome LeetCode Solution

class Solution {
    private Boolean isPrime(int n) {
        for(int i=2; i<=Math.sqrt(n);i++) {
            if(n%i==0) return false;
        }
        return true;
    }

    private int reverse(int n){
        int m = 0;
        while (n>0) {
            m = m*10 + n % 10;
            n /= 10;
        }
        return m;
    }
    
    private Boolean isPalindrome(int n){
        return n== reverse(n);
    }
    public int primePalindrome(int n) {
        if( n <= 2) return 2;
        
        if(n>=1e7 && n<=1e8) {
            n=100030001;
        }
        
        if(n%2==0) n++;
        
        for(int i=n; i>=n; i+=2){
            if(isPalindrome(i)) 
                if(isPrime(i)) return i;
        }
        return -1;
    }
}

Complexity Analysis

  • Time Complexity: O(n*logn*sqrt(n))
    • The loop runs for n/2 times taking O(n/2) time ie. O(n) This calls 2 functions isPrime and isPalindrome
    • isPrime takes O(sqrt(n)) time
    • isPalindrome takes O(logn) time
  • Space complexity: O(1)
    • no extra space is required
Translate »