We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Prime Palindrome

Number: 897

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an integer n, return the smallest prime palindrome greater than or equal to n. An integer is considered prime if it has exactly two divisors (1 and itself) and is a palindrome if it reads the same forwards and backwards. It is guaranteed that an answer exists within the range [2, 2 * 10^8].

Key Insights

  • A naive brute force can work by checking every number starting from n, but optimizations improve efficiency.
  • Only odd-length palindromes (except for the number 11) need to be considered because even-length palindromes (other than 11) are divisible by 11.
  • Efficient prime checking using trial division up to the square root of the candidate minimizes unnecessary computation.
  • Early handling of small base cases (like n <= 11) can simplify the logic.

Space and Time Complexity

Time Complexity: In the worst-case, for each candidate palindrome we perform a prime check in O(√p) time; however, by skipping non-promising candidates (even-length palindromes), the practical runtime is significantly better. Space Complexity: O(1) as we only use a constant amount of extra memory.

Solution

We begin by checking special cases for n ≤ 11 since these can be directly returned if they already satisfy the conditions. For numbers greater than 11, we generate candidates one by one and check two properties:

  1. Whether the number is a palindrome.
  2. Whether the number is prime (using trial division up to its square root).

For efficiency, we note that apart from 11, any even-digit palindrome is divisible by 11 and thus not prime. This allows us to potentially skip large segments of candidates or directly generate only odd-length palindromes. The algorithm loops through candidates starting from n upward until it finds one that satisfies both conditions.

The data structures used are simple variables and helper functions for clarity and segmentation of the palindrome and prime checks.

Code Solutions

def is_palindrome(num):
    # Convert the number to string and check if it reads the same forwards and backwards.
    s = str(num)
    return s == s[::-1]

def is_prime(num):
    # Base cases for 1 and 2.
    if num < 2:
        return False
    if num == 2:
        return True
    # Eliminate even numbers greater than 2.
    if num % 2 == 0:
        return False
    # Only check for factors up to the square root of num.
    i = 3
    while i * i <= num:
        if num % i == 0:
            return False
        i += 2
    return True

def prime_palindrome(n):
    # Special cases: numbers less than or equal to 11.
    if n <= 2:
        return 2
    if n <= 3:
        return 3
    if n <= 5:
        return 5
    if n <= 7:
        return 7
    if n <= 11:
        return 11

    candidate = n
    # Loop indefinitely until the candidate is both a palindrome and prime.
    while True:
        # Skip even-digit palindromes (except for 11) because they are divisible by 11.
        if is_palindrome(candidate) and is_prime(candidate):
            return candidate
        candidate += 1

# You can test the solution with sample inputs:
print(prime_palindrome(6))   # Expected output: 7
print(prime_palindrome(8))   # Expected output: 11
print(prime_palindrome(13))  # Expected output: 101
← Back to All Questions