algoadvance

Leetcode 866. Prime Palindrome

Problem Statement

Given an integer N, find the smallest prime palindrome greater than or equal to N.

A prime number is a number that is greater than 1 and has no divisors other than 1 and itself. A palindrome is a number that reads the same backwards as forwards.

Clarifying Questions

  1. Input Range: What is the range of the input integer N?
    • The input could be any non-negative integer.
  2. Output: What should be returned if there is no prime palindrome (although theoretically, such a case wouldn’t exist)?
    • Return the smallest prime palindrome greater than or equal to N.
  3. Performance: Are there any performance constraints we should be aware of?
    • We should aim for an efficient solution but should first clarify the theoretical constraints around the search space.

With these questions in mind, let’s move on to the strategy.

Strategy

  1. Palindrome Check: Create a function to check if a number is a palindrome.
  2. Prime Check: Create a function to check if a number is a prime.
  3. Search Loop: Starting from N, increment each number and check if both conditions (prime and palindrome) are met.
    • Optimization: Splitting into even and odd length palindromes will help in avoiding some unnecessary checks, as all even-length palindromes are divisible by 11 except for 11 itself.

Code

public class Solution {

    public int primePalindrome(int N) {
        // Special case when N is less than 8, as those constant numbers need special treatment
        if (N <= 2) return 2;
        if (N <= 3) return 3;
        if (N <= 5) return 5;
        if (N <= 7) return 7;
        
        // If N is between 7 and 11, return the prime number which is 11.
        if (N <= 11) return 11;

        while (true) {
            // Skip even length palindromes greater than 11 since they are multiples of 11.
            if (10_000_000 < N && N < 100_000_000) {
                N = 100_000_001;
            }

            if (isPalindrome(N) && isPrime(N)) {
                return N;
            }
            N++;
        }
    }

    private boolean isPalindrome(int x) {
        String str = Integer.toString(x);
        int len = str.length();
        
        for (int i = 0; i < len / 2; i++) {
            if (str.charAt(i) != str.charAt(len - i - 1)) {
                return false;
            }
        }
        return true;
    }

    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;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.primePalindrome(31)); // Example for testing
    }
}

Time Complexity

Overall, the approach effectively leans on incremental search but leverages palindromic and prime checks intelligently. The solution is efficient for reasonably large N, but the worst case is always bounded by the prime distribution and palindromic nature harmony.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI