Jobs

Interviews

Discussions

Prime Palindrome

Medium

Asked by:

11 views

Topics:

ArraysStringsTwo Pointers

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⁸

Try coding it in LeetCode

Prime Palindrome

Medium

Asked by:

11 views

Topics:

ArraysStringsTwo Pointers

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⁸

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the upper bound for the number we need to check for prime palindromes?
Should I return the largest prime palindrome less than or equal to the upper bound, or the smallest one greater than or equal to a given input?
What should I return if no prime palindrome exists within the specified range (if one is given)?
Is the input guaranteed to be an integer, and should I validate the input?
Can you provide a few example inputs and their expected outputs to ensure I understand the requirements correctly?

Brute Force Solution

Approach

The brute force method for finding a prime palindrome involves checking every number within a specified range. We test each number to see if it's both a prime number and a palindrome. If it is, we've found a potential solution.

Here's how the algorithm would work step-by-step:

Start with the smallest number in our search range.
Check if the current number is a palindrome. A palindrome reads the same forwards and backward.
If it is a palindrome, then check if it is a prime number. A prime number is only divisible by 1 and itself.
If the number is both a palindrome and a prime, record it as a possible answer.
Move to the next number in our range and repeat the process.
Continue until we've checked all numbers in the range.
If we've found any numbers that are both palindromes and prime, pick the biggest one as the answer.

Code Implementation

def find_largest_prime_palindrome_brute_force(max_number):
    largest_prime_palindrome = 0

    for current_number in range(2, max_number + 1):
        # First, check if the number is a palindrome
        if str(current_number) == str(current_number)[::-1]:

            # If it is a palindrome, then check if it is prime
            is_prime = True
            for possible_divisor in range(2, int(current_number**0.5) + 1):
                if current_number % possible_divisor == 0:
                    is_prime = False
                    break

            #If current number is prime, update result
            if is_prime:

                largest_prime_palindrome = current_number

    return largest_prime_palindrome

Big(O) Analysis

Time Complexity

O(n * sqrt(n)) – The algorithm iterates through a range of numbers up to n. For each number, it first checks if it's a palindrome, which takes O(log n) time in terms of number of digits. If the number is a palindrome, the algorithm proceeds to check if it's prime. The primality test involves iterating up to the square root of the number, which is sqrt(n). Therefore, the overall time complexity is O(n * (log n + sqrt(n))). Since sqrt(n) dominates log n for large n, the time complexity can be simplified to O(n * sqrt(n)).

Space Complexity

O(1) – The provided algorithm checks each number within a given range for primality and palindromicity. It only needs to store a few variables to represent the current number being checked, a flag for whether it's a palindrome, a flag for whether it's prime, and potentially the largest prime palindrome found so far. These variables require constant space, independent of the size of the range (which we can consider as N). Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

To find the largest prime palindrome under a given number, we want to avoid checking every number. Instead, we will generate palindromes and then check if they are prime, focusing on larger palindromes first since we want the largest one.

Here's how the algorithm would work step-by-step:

Start by generating palindromes with the maximum possible number of digits (same as the number of digits of the input number).
Check if the generated palindrome is prime. If it is, you've found your answer; stop here.
If the palindrome is not prime, or if you didn't find any prime palindromes with that many digits, proceed to generate palindromes with one fewer digit.
Repeat the process of generating palindromes and checking for primality, reducing the number of digits each time, until you find a prime palindrome.
A useful shortcut is to note that all even-digit palindromes are divisible by 11. This means they can't be prime (except for 11 itself). Therefore, you can skip generating even-digit palindromes, vastly reducing your search space.
When generating odd-digit palindromes, focus on the largest possibilities first. This increases the chance of finding the largest prime palindrome quickly.
If you run out of digits to check (i.e., reach single-digit numbers), return the largest single-digit prime number, which is 7, assuming the input allows it.

Code Implementation

def prime_palindrome(number):
    for digits in range(len(str(number)), 0, -1):
        # Skip even-digit palindromes as they are divisible by 11.
        if digits % 2 == 0:
            continue

        start = 10**(digits // 2)
        end = 10**(digits // 2 + 1)

        for i in range(end - 1, start - 1, -1):
            palindrome = int(str(i) + str(i)[:digits // 2][::-1])

            if palindrome >= number:
                continue

            if is_prime(palindrome):
                return palindrome

    # Return 7 if no prime palindrome is found.
    return 7

def is_prime(number):
    if number < 2:
        return False
    for i in range(2, int(number**0.5) + 1):
        if number % i == 0:
            return False
    return True

Big(O) Analysis

Time Complexity

O(n^(1/2) * 10^(n/2)) – The outer loop implicitly iterates through different digit lengths, starting from the input's digit length down to single digits, focusing mainly on odd lengths since even-length palindromes are mostly skipped. The dominant cost comes from generating odd-digit palindromes which can be approximated as 10^(n/2), where n is the number of digits. For each generated palindrome, a primality test is performed, which has a time complexity of O(sqrt(palindrome)), which can be approximated as O(n^(1/2)) since the maximum value of palindrome is close to input n. Hence the time complexity is O(n^(1/2) * 10^(n/2)).

Space Complexity

O(log N) – The space complexity is determined by the recursion depth when generating palindromes, and the space needed to store the generated palindromes as strings for primality testing. Since we are reducing the number of digits to generate palindromes, the number of recursive calls is proportional to the number of digits in N, which is log N. The maximum size of the palindrome string will also be related to the number of digits of N which is log N. Therefore, the auxiliary space complexity is O(log N).

Edge Cases

Case	How to Handle
Input 'n' is less than 2	Return an empty list because no single-digit or zero-digit prime palindromes exist.
Large input 'n' approaching maximum integer value	Use an efficient prime checking algorithm and palindrome generation technique to avoid excessive computation and potential timeouts.
No prime palindrome exists within the specified range [2, n]	Return an empty list to indicate that no valid prime palindrome was found.
Integer overflow during palindrome generation or prime checking	Use a data type that can accommodate larger numbers (e.g., long) or implement checks to prevent overflow.
Input 'n' is a prime palindrome itself	Include 'n' in the returned list if it satisfies both the prime and palindrome properties.
Memory constraints when generating a large sequence of numbers to check	Optimize the algorithm to avoid storing all numbers in memory at once, checking primality and palindromicity on the fly.
Input 'n' is a negative number	Return an empty list or throw an exception, as prime numbers are not defined for negative values.
The upper limit n contains only one repeated digit, for example 1111	Efficiently skip these ranges to improve performance since many composite palindromes consist of repeated digits.

Input 'n' is less than 2

How to Handle:

Return an empty list because no single-digit or zero-digit prime palindromes exist.

Large input 'n' approaching maximum integer value

How to Handle:

Use an efficient prime checking algorithm and palindrome generation technique to avoid excessive computation and potential timeouts.

No prime palindrome exists within the specified range [2, n]

How to Handle:

Return an empty list to indicate that no valid prime palindrome was found.

Integer overflow during palindrome generation or prime checking

How to Handle:

Use a data type that can accommodate larger numbers (e.g., long) or implement checks to prevent overflow.

Input 'n' is a prime palindrome itself

How to Handle:

Include 'n' in the returned list if it satisfies both the prime and palindrome properties.

Memory constraints when generating a large sequence of numbers to check

How to Handle:

Optimize the algorithm to avoid storing all numbers in memory at once, checking primality and palindromicity on the fly.

Input 'n' is a negative number

How to Handle:

Return an empty list or throw an exception, as prime numbers are not defined for negative values.

The upper limit n contains only one repeated digit, for example 1111

How to Handle:

Efficiently skip these ranges to improve performance since many composite palindromes consist of repeated digits.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the upper bound for the number we need to check for prime palindromes?
Should I return the largest prime palindrome less than or equal to the upper bound, or the smallest one greater than or equal to a given input?
What should I return if no prime palindrome exists within the specified range (if one is given)?
Is the input guaranteed to be an integer, and should I validate the input?
Can you provide a few example inputs and their expected outputs to ensure I understand the requirements correctly?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the smallest number in our search range.
Check if the current number is a palindrome. A palindrome reads the same forwards and backward.
If it is a palindrome, then check if it is a prime number. A prime number is only divisible by 1 and itself.
If the number is both a palindrome and a prime, record it as a possible answer.
Move to the next number in our range and repeat the process.
Continue until we've checked all numbers in the range.
If we've found any numbers that are both palindromes and prime, pick the biggest one as the answer.

Code Implementation

def find_largest_prime_palindrome_brute_force(max_number):
    largest_prime_palindrome = 0

    for current_number in range(2, max_number + 1):
        # First, check if the number is a palindrome
        if str(current_number) == str(current_number)[::-1]:

            # If it is a palindrome, then check if it is prime
            is_prime = True
            for possible_divisor in range(2, int(current_number**0.5) + 1):
                if current_number % possible_divisor == 0:
                    is_prime = False
                    break

            #If current number is prime, update result
            if is_prime:

                largest_prime_palindrome = current_number

    return largest_prime_palindrome

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start by generating palindromes with the maximum possible number of digits (same as the number of digits of the input number).
Check if the generated palindrome is prime. If it is, you've found your answer; stop here.
If the palindrome is not prime, or if you didn't find any prime palindromes with that many digits, proceed to generate palindromes with one fewer digit.
Repeat the process of generating palindromes and checking for primality, reducing the number of digits each time, until you find a prime palindrome.
A useful shortcut is to note that all even-digit palindromes are divisible by 11. This means they can't be prime (except for 11 itself). Therefore, you can skip generating even-digit palindromes, vastly reducing your search space.
When generating odd-digit palindromes, focus on the largest possibilities first. This increases the chance of finding the largest prime palindrome quickly.
If you run out of digits to check (i.e., reach single-digit numbers), return the largest single-digit prime number, which is 7, assuming the input allows it.

Code Implementation

def prime_palindrome(number):
    for digits in range(len(str(number)), 0, -1):
        # Skip even-digit palindromes as they are divisible by 11.
        if digits % 2 == 0:
            continue

        start = 10**(digits // 2)
        end = 10**(digits // 2 + 1)

        for i in range(end - 1, start - 1, -1):
            palindrome = int(str(i) + str(i)[:digits // 2][::-1])

            if palindrome >= number:
                continue

            if is_prime(palindrome):
                return palindrome

    # Return 7 if no prime palindrome is found.
    return 7

def is_prime(number):
    if number < 2:
        return False
    for i in range(2, int(number**0.5) + 1):
        if number % i == 0:
            return False
    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input 'n' is less than 2	Return an empty list because no single-digit or zero-digit prime palindromes exist.
Large input 'n' approaching maximum integer value	Use an efficient prime checking algorithm and palindrome generation technique to avoid excessive computation and potential timeouts.
No prime palindrome exists within the specified range [2, n]	Return an empty list to indicate that no valid prime palindrome was found.
Integer overflow during palindrome generation or prime checking	Use a data type that can accommodate larger numbers (e.g., long) or implement checks to prevent overflow.
Input 'n' is a prime palindrome itself	Include 'n' in the returned list if it satisfies both the prime and palindrome properties.
Memory constraints when generating a large sequence of numbers to check	Optimize the algorithm to avoid storing all numbers in memory at once, checking primality and palindromicity on the fly.
Input 'n' is a negative number	Return an empty list or throw an exception, as prime numbers are not defined for negative values.
The upper limit n contains only one repeated digit, for example 1111	Efficiently skip these ranges to improve performance since many composite palindromes consist of repeated digits.

Input 'n' is less than 2

How to Handle:

Return an empty list because no single-digit or zero-digit prime palindromes exist.

Large input 'n' approaching maximum integer value

How to Handle:

Use an efficient prime checking algorithm and palindrome generation technique to avoid excessive computation and potential timeouts.

No prime palindrome exists within the specified range [2, n]

How to Handle:

Return an empty list to indicate that no valid prime palindrome was found.

Integer overflow during palindrome generation or prime checking

How to Handle:

Use a data type that can accommodate larger numbers (e.g., long) or implement checks to prevent overflow.

Input 'n' is a prime palindrome itself

How to Handle:

Include 'n' in the returned list if it satisfies both the prime and palindrome properties.

Memory constraints when generating a large sequence of numbers to check

How to Handle:

Optimize the algorithm to avoid storing all numbers in memory at once, checking primality and palindromicity on the fly.

Input 'n' is a negative number

How to Handle:

Return an empty list or throw an exception, as prime numbers are not defined for negative values.

The upper limit n contains only one repeated digit, for example 1111

How to Handle:

Efficiently skip these ranges to improve performance since many composite palindromes consist of repeated digits.