algoadvance

Leetcode 866. Prime Palindrome

Problem Statement

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. An integer is a palindrome if it reads the same from the left and right.

Example:

• Input: n = 13

• Output: 101

  Explanation: 101 is a prime number and also a palindrome.

Constraints:

• 1 <= n <= 10^8
• The result will be in the range [2, 2 * 10^8].

Clarifying Questions

1. Should the function throw an error or provide any specific message for inputs out of the specified range (1 <= n <= 10^8)?
2. Should the function handle performance optimizations for large values of n or is the brute force approach acceptable in terms of the problem constraints?

Let’s assume that the inputs will always be within the provided constraints, and we should handle large values efficiently.

Strategy

1. Palindrome Function: Implement a function to check if a number is a palindrome.
2. Prime Checker: Implement a function to check if a number is prime.
3. Iterate to Find the Result: Start from n and look for the next number that is both a palindrome and prime.

Code

#include <iostream>
#include <cmath>

// Check if a number is a palindrome
bool isPalindrome(int x) {
    // Convert number to string
    std::string s = std::to_string(x);
    int left = 0, right = s.size() - 1;
    
    // Check symmetrical characters
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

// Check if a number is prime
bool isPrime(int x) {
    if (x < 2) return false;
    if (x == 2 || x == 3) return true;
    if (x % 2 == 0 || x % 3 == 0) return false;

    for (int i = 5; i * i <= x; i += 6) {
        if (x % i == 0 || x % (i + 2) == 0) return false;
    }
    return true;
}

// Main function to find the smallest prime palindrome greater than or equal to n
int primePalindrome(int n) {
    // To handle edge cases efficiently directly
    if (1 <= n && n <= 2) return 2;
    if (n == 3) return 3;
    if (n == 4) return 5;
    if (n == 5) return 5;

    // Start searching from the next odd number if n is even
    if (n % 2 == 0) n++;

    while (true) {
        if (isPalindrome(n) && isPrime(n)) return n;
        n += 2; // Increment by 2 to stay in the range of odd numbers
        if (n > 1e7 && n < 2e7) n = 1e8 + 1; // Skip direct leap for a valid range edge case
    }
}

int main() {
    int n;
    std::cin >> n;
    std::cout << primePalindrome(n) << std::endl;
    return 0;
}

Time Complexity

• Palindrome Check: O(log10(n)) due to string conversion and comparison.
• Prime Check: O(sqrt(n)) due to the loop up to the square root of n.
• Main Function: In the worst case, it could go through many numbers, but by skipping unwanted ranges (like even numbers), the solution remains efficient in finding the next prime palindrome.

Space Complexity

• O(log10(n)) for the palindrome check due to string conversion storage.

This strategy ensures we balance simplicity and performance to solve the problem within the given constraints efficiently.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?