866. Prime Palindrome

MediumMath
Leetcode Link

Problem Description

The problem requires us to find the smallest prime palindrome greater than or equal to a given integer n. A prime palindrome is an integer that is both a prime number and a palindrome. A prime number is one that has exactly two distinct positive divisors: 1 and itself, whereas a palindrome is a number that reads the same backward as forward. For instance, 2, 3, 5, 7, 11 are prime numbers, and 101, 131, 151 are examples of prime palindromes.

Intuition

The brute force method is to search for prime palindromes starting at n and proceeding to larger numbers until we find the smallest prime palindrome. To check if a number is a palindrome, we reverse it and see if it's equal to the original number. For example, reversing 12321 would yield the same number, confirming it's a palindrome. To verify if a number is prime, we check if it's divisible by any number other than 1 and itself, which we can efficiently do by checking divisibility only up to the square root of the number.

We start from n and incrementally check each number for both primality and palindromicity. However, there's an optimization to be noted: there are no eight-digit palindromes which are prime because all multiples of 11 are non-prime, and any number with an even number of digits that's a palindrome is a multiple of 11. Therefore, if n falls in the range of eight-digit numbers (10^7 to 10^8), we can skip all of those and jump directly to 10^8, which is the start of the nine-digit numbers. This optimization significantly reduces the number of checks for larger values of n.

By combining these checks and the mentioned optimization, we can iteratively find the smallest prime palindrome greater than or equal to n.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

The solution provided in the Python code implements a brute-force approach to find the smallest prime palindrome. The code provides two helper functions, is_prime and reverse, to help with this process.

  • The is_prime function checks the primality of a number. A number is prime if it is not divisible by any number other than 1 and itself. To determine if a number x is prime, the function iterates from 2 to sqrt(x) and checks if x is divisible by any of these numbers. If a divisor is found, the function returns False, otherwise, after completing the loop, it returns True.

  • The reverse function receives a number x and returns its reversed form. This is achieved by continuously extracting the last digit of x and appending it to a new number res, while also reducing x by a factor of 10 each time.

These helper functions are utilized in the main function primePalindrome. The main loop runs indefinitely (while 1:), incrementally checking whether the current number n is a palindromic prime:

  1. The loop starts by checking if n is a palindrome by comparing it to the result of reverse(n).
  2. If n is a palindrome, the loop proceeds to check if it is prime using the is_prime function.
  3. If n satisfies both conditions (palindromicity and primality), it is returned as the solution and the loop ends.

There is a key optimization in this loop: if n falls within the range 10^7 < n < 10^8, the function jumps n directly to 10^8. As mentioned earlier, since all palindromic numbers with an even number of digits are non-prime (they are divisible by 11), it is pointless to check any number within the range of eight digits. This optimization saves computational time by avoiding unnecessary checks.

After each iteration, if no palindrome prime is found, n is incremented (n += 1) and the loop continues with the new incremented value.

By using these functions and the while loop, the solution effectively searches through the space of numbers greater than or equal to n until it finds the condition-satisfying prime palindrome.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search can be used to find whether two components in a graph are connected.

Example Walkthrough

Let's walk through a simple example using the solution approach to find the smallest prime palindrome greater than or equal to ( n = 31 ).

  1. Start from ( n = 31 ) and check if it is a palindrome by using the reverse function. Reverse of 31 is 13 which is not equal to 31, so it is not a palindrome.

  2. Since 31 is not a palindrome, increment ( n ) to 32 and repeat the process.

  3. At ( n = 32 ), it is not a palindrome (reverse is 23). Increment ( n ) to 33.

  4. At ( n = 33 ), it is a palindrome as its reverse is also 33. However, 33 is not prime (it is divisible by 3 and 11), so move to the next number.

  5. Proceeding in this manner, increment ( n ) and check for both palindromicity and primality.

  6. Upon reaching ( n = 101 ), we find that it is a palindrome since its reverse is also 101.

  7. Now, we use the is_prime function to check if 101 is prime. Since 101 has no divisors other than 1 and itself, it is prime.

  8. As ( n = 101 ) satisfies both conditions of being a palindrome and prime, the loop ends and 101 is returned as the solution.

In this example, the smallest prime palindrome greater than or equal to 31 is 101. The optimization regarding the eight-digit numbers was not needed here since our ( n ) was far below that range. However, if our starting ( n ) had been within the range of ( 10^7 ) to ( 10^8 ), we would have directly jumped to ( 10^8 ) as the starting point.

Solution Implementation

1class Solution:
2    def prime_palindrome(self, n: int) -> int:
3        # Helper function to check if a number is prime.
4        def is_prime(x):
5            if x < 2:
6                return False
7            divisor = 2
8            # Check divisors up to the square root of x.
9            while divisor * divisor <= x:
10                if x % divisor == 0:
11                    return False
12                divisor += 1
13            return True
14
15        # Helper function to reverse an integer number.
16        def reverse(x):
17            result = 0
18            while x:
19                result = result * 10 + x % 10  # Add the last digit of x to result.
20                x //= 10  # Remove the last digit of x.
21            return result
22
23        # Loop until we find the palindrome prime.
24        while True:
25            # Check if the number is both a palindrome and prime.
26            if reverse(n) == n and is_prime(n):
27                return n
28            # Skip all numbers between 10^7 and 10^8, as there are no 8-digit palindrome primes.
29            if 10**7 < n < 10**8:
30                n = 10**8
31            n += 1  # Go to the next number.
32
33# Note that the method name 'primePalindrome' has been changed to 'prime_palindrome' to conform to Python naming conventions (snake_case for function names).
34# However, it's important not to change method names when they are part of a predefined interface.
35# Since here the request was explicit to not modify method names, the correct approach would be to leave the original method name as is.
36
1class Solution {
2
3    /**
4     * Finds the smallest prime palindrome greater than or equal to N.
5     *
6     * @param n the number to find the prime palindrome for
7     * @return the smallest prime palindrome greater than or equal to n
8     */
9    public int primePalindrome(int n) {
10        while (true) {
11            // If the number is a palindrome and prime, return it.
12            if (isPalindrome(n) && isPrime(n)) {
13                return n;
14            }
15            // Skip the non-palindrome range since there is no 8-digit palindrome prime.
16            if (n > 10_000_000 && n < 100_000_000) {
17                n = 100_000_000;
18            }
19            // Increment the number to check the next one.
20            n++;
21        }
22    }
23
24    /**
25     * Checks if the number is prime.
26     *
27     * @param x the number to be checked
28     * @return true if x is prime, otherwise false
29     */
30    private boolean isPrime(int x) {
31        if (x < 2) {
32            return false;
33        }
34        // Check divisibility by numbers up to the square root of x.
35        for (int i = 2; i * i <= x; ++i) {
36            if (x % i == 0) {
37                return false; // Found a divisor, hence x is not prime.
38            }
39        }
40        return true; // No divisors found, so x is prime.
41    }
42
43    /**
44     * Checks if the number is a palindrome.
45     *
46     * @param x the number to be checked
47     * @return true if x is a palindrome, otherwise false
48     */
49    private int isPalindrome(int x) {
50        int reverse = 0;
51        int original = x;
52        while (x != 0) {
53            reverse = reverse * 10 + x % 10; // Reversing the digits of x.
54            x /= 10; // Removing the last digit from x.
55        }
56        // If the reversed number is the same as the original, it's a palindrome.
57        return reverse == original;
58    }
59
60}
61
1class Solution {
2public:
3    // Main function to find the smallest prime palindrome greater than or equal to N
4    int primePalindrome(int N) {
5        while (true) {
6            // Check if the current number N is palindrome and prime
7            if (isPalindrome(N) && isPrime(N)) {
8                return N; // Return the number if it's a prime palindrome
9            }
10            // If N is between 10^7 and 10^8, skip ahead to 10^8
11            // because we know there are no 8-digit palindromes that are prime
12            if (N > 1e7 && N < 1e8) {
13                N = static_cast<int>(1e8);
14            }
15            ++N; // Move on to the next number
16        }
17    }
18
19    // Helper function to check if a number is prime
20    bool isPrime(int x) {
21        if (x < 2) return false; // Numbers less than 2 are not prime
22        for (int i = 2; i * i <= x; ++i) {
23            if (x % i == 0)
24                return false; // If divisible by i, x is not prime
25        }
26        return true; // If no divisors were found, x is prime
27    }
28
29    // Helper function to check if a number is a palindrome
30    int isPalindrome(int x) {
31        int original = x;
32        int reversed = 0;
33        while (x > 0) {
34            reversed = reversed * 10 + x % 10; // Append the last digit of x to the reversed number
35            x /= 10; // Remove the last digit from x
36        }
37        return reversed == original; // A palindrome number reads the same forwards and backwards
38    }
39};
40
1// Function to check if a number is prime
2function isPrime(x: number): boolean {
3    if (x < 2) return false; // Numbers less than 2 are not prime
4    for (let i = 2; i * i <= x; i++) {
5        if (x % i === 0) return false; // If divisible by i, x is not prime
6    }
7    return true; // If no divisors were found, x is prime
8}
9
10// Function to check if a number is a palindrome
11function isPalindrome(x: number): boolean {
12    let original = x;
13    let reversed = 0;
14    while (x > 0) {
15        reversed = reversed * 10 + x % 10; // Append the last digit of x to the reversed number
16        x = Math.floor(x / 10); // Remove the last digit from x
17    }
18    return reversed === original; // A palindrome number reads the same forwards and backwards
19}
20
21// Main function to find the smallest prime palindrome greater than or equal to N
22function primePalindrome(N: number): number {
23    while (true) {
24        // Check if the current number N is a palindrome and prime
25        if (isPalindrome(N) && isPrime(N)) {
26            return N; // Return the number if it's a prime palindrome
27        }
28        // If N is between 10^7 and 10^8, skip ahead to 10^8
29        // because there are no 8-digit palindromes that are prime
30        if (N > 1e7 && N < 1e8) {
31            N = 1e8;
32        }
33        N++; // Move on to the next number
34    }
35}
36
37// Usage example:
38// let result = primePalindrome(31);
39// console.log(result); // Logs the smallest prime palindrome greater than or equal to 31
40
Not Sure What to Study? Take the 2-min Quiz：

Which algorithm should you use to find a node that is close to the root of the tree?

Time and Space Complexity

Time Complexity

The key operations of the algorithm include the checking of whether a number is a palindrome (reverse(n) == n), and whether it is prime (is_prime(x)).

  1. Palindrome Check: The time complexity for checking if n is a palindrome is O(log n) since it involves iterating each digit of the number once.

  2. Prime Check: The prime checking function has a time complexity of O(sqrt(x)) because it checks all numbers up to the square root of x to determine if x is prime.

When combining the palindrome and prime checks, the overall time complexity is not simply the product of the two. We must consider how far the loop will iterate to find the next prime palindrome. The loop will continue until it finds a prime palindrome, which is done in increasing order from n. There is an optimization at if 10**7 < n < 10**8: n = 10**8, which skips non-palindromic numbers within that range as no 8-digit palindrome can be a prime (all even-digit palindromes are divisible by 11).

However, the worst-case scenario involves checking numbers until the next prime palindrome is found. Since the distance between prime numbers can generally be considered O(n) for the space we are interested in, and the next palindrome can also be O(n) away from the current one, combined with our checks, the worst-case complexity can be described as O(n * sqrt(n)).

Space Complexity

The space complexity of the algorithm is O(1). There is a constant amount of extra space used:

  • A finite number of integer variables are used (n, v, x, res), and
  • No additional data structures that grow with the input size are utilized.

Therefore, the space complexity does not depend on the input size and remains constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the most two important steps in writing a depth first search function? (Select 2)

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫