866. Prime Palindrome Solution & Explanation

Q: Is Prime Palindrome easy or hard?

Prime Palindrome is typically considered a medium-level problem. The brute force idea is simple, but the optimized solution requires recognizing that even-length palindromes greater than 11 cannot be prime and generating palindrome candidates efficiently.

Q: How to solve Prime Palindrome efficiently?

Generate palindromes instead of checking every integer. Build odd-length palindromes by mirroring the first half of the number, then run a primality test using trial division up to sqrt(x). Skip even-length palindromes larger than 11 because they are always divisible by 11.

Q: What is the best approach for Prime Palindrome?

The most efficient approach generates palindrome numbers directly and then checks if they are prime. Instead of scanning every integer, you construct palindromes by mirroring digits and run a primality test on each candidate. Skipping even-length palindromes (except 11) further reduces the search space.

Q: Is Prime Palindrome asked at Google/Amazon/Meta?

Prime Palindrome represents the type of number theory and math-heavy question sometimes seen in interviews at companies like Google or Amazon. It tests knowledge of palindrome construction, prime testing, and optimization through mathematical observations.

Q: What data structure is used in Prime Palindrome?

The problem mainly relies on mathematical operations rather than complex data structures. String manipulation or integer digit operations are used to construct and check palindromes, while a simple loop performs the primality test.

Q: What is the time complexity of Prime Palindrome?

The brute force method runs in roughly O(k * sqrt(n)) because each candidate number requires a primality test up to sqrt(n). The optimized approach generates only palindrome candidates and checks primality, giving an effective complexity around O(P * sqrt(P)), where P is the candidate palindrome size.

Q: Prime Palindrome Python or Java solution approach?

Most Python or Java solutions generate palindrome candidates and then verify primality with a sqrt-based check. This avoids iterating through every integer and significantly improves performance compared with brute force scanning.

The problem

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⁸

Approach overview

Problem Overview: Given an integer n, return the smallest number greater than or equal to n that is both a palindrome and a prime. A palindrome reads the same forward and backward, while a prime number has exactly two divisors: 1 and itself.

Approach 1: Brute Force Search (Time: O(k * sqrt(n)), Space: O(1))

Start at n and iterate upward one number at a time. For every number, first check if it is a palindrome by converting it to a string and comparing it with its reverse, or by using two pointers from both ends. If the number is a palindrome, run a primality test by checking divisibility from 2 to sqrt(x). The first number that satisfies both conditions is the answer.

This method is straightforward and mirrors the problem definition. However, most integers are neither palindromes nor primes, so the algorithm wastes time checking many candidates. As n grows, the density of primes decreases and brute-force iteration becomes slow.

Approach 2: Optimized Palindrome Generation + Prime Check (Time: ~O(P * sqrt(P)), Space: O(1))

Instead of checking every number, generate only palindrome candidates. Construct palindromes by building the first half of the number and mirroring it to form the second half. This drastically reduces the search space because you skip all non-palindrome integers entirely.

A key observation from math and number theory: every even-length palindrome greater than 11 is divisible by 11, so it cannot be prime. The optimized approach therefore generates only odd-length palindromes (except the special case 11). For each generated palindrome, run a standard primality test using trial division up to sqrt(x). As soon as you find one that is both ≥ n and prime, return it.

This approach reduces the candidate space by orders of magnitude. Instead of scanning every integer, you jump directly between palindrome numbers and only perform primality checks on those candidates.

Recommended for interviews: The optimized palindrome-generation approach is what interviewers typically expect. Brute force demonstrates that you understand palindrome detection and primality testing, but generating palindromes directly shows stronger problem-solving ability and knowledge of number properties.

Approach 1: Brute Force Approach

The brute force approach involves incrementing from the given number n until we find a number that is both a palindrome and a prime. This approach checks every number to see if it is a palindrome and, if it is, checks if it is a prime number.

This is not the most efficient solution since it checks every number in succession, but it is straightforward and easy to implement.

Python

def is_palindrome(x):
    return str(x) == str(x)[::-1]

def is_prime(x):
    if x < 2:
        return False
    if x in (2, 3):
        return True
    if x % 2 == 0 or x % 3 == 0:
        return False
    i = 5
    while i * i <= x:
        if x % i == 0 or x % (i + 2) == 0:
            return False
        i += 6
    return True

def smallest_prime_palindrome(n):
    while True:
        if is_palindrome(n) and is_prime(n):
            return n
        n += 1

Java

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

    private static boolean isPrime(int x) {
        if (x < 2) return false;
        if (x == 2) return true;
        if (x % 2 == 0) return false;
        for (int i = 3; i * i <= x; i += 2) {
            if (x % i == 0) return false;
        }
        return true;
    }

    public int smallestPrimePalindrome(int n) {
        while (true) {
            if (isPalindrome(n) && isPrime(n)) return n;
            n++;
        }
    }
}

C++

#include <iostream>
#include <cmath>
#include <string>

bool is_palindrome(int x) {
    std::string s = std::to_string(x);
    std::string r = s;
    std::reverse(r.begin(), r.end());
    return s == r;
}

bool is_prime(int x) {
    if (x < 2) return false;
    if (x == 2) return true;
    if (x % 2 == 0) return false;
    for (int i = 3; i * i <= x; i += 2) {
        if (x % i == 0) return false;
    }
    return true;
}

int smallest_prime_palindrome(int n) {
    while (true) {
        if (is_palindrome(n) && is_prime(n)) { return n; }
        n++;
    }
}

JavaScript

function isPalindrome(x) {
    const s = x.toString();
    const len = s.length;
    for (let i = 0; i < len / 2; i++) {
        if (s[i] != s[len - 1 - i]) {
            return false;
        }
    }
    return true;
}

function isPrime(x) {
    if (x < 2) return false;
    if (x === 2) return true;
    if (x % 2 === 0) return false;
    for (let i = 3; i * i <= x; i += 2) {
        if (x % i === 0) return false;
    }
    return true;
}

function smallestPrimePalindrome(n) {
    while (true) {
        if (isPalindrome(n) && isPrime(n)) {
            return n;
        }
        n++;
    }
}

using System;

public class Solution {
    private static bool IsPalindrome(int x) {
        char[] s = x.ToString().ToCharArray();
        Array.Reverse(s);
        return new string(s) == x.ToString();
    }

    private static bool IsPrime(int x) {
        if (x < 2) return false;
        if (x == 2) return true;
        if (x % 2 == 0) return false;
        for (int i = 3; i * i <= x; i += 2) {
            if (x % i == 0) return false;
        }
        return true;
    }

    public int SmallestPrimePalindrome(int n) {
        while (true) {
            if (IsPalindrome(n) && IsPrime(n)) return n;
            n++;
        }
    }
}

The smallest_prime_palindrome function starts at n and increases until it finds a number that is both a palindrome and a prime. is_palindrome checks if the number is a palindrome by converting it to a string and comparing it to its reverse. is_prime uses trial division to determine if a number is prime. This includes checks for small prime divisors to enhance efficiency.

Complexity

Time complexity: Generally O(n * sqrt(n)), because for each number until the next prime palindrome, we may need to check its primality which takes sqrt(n) time.
Space complexity: O(1), as no additional data structures are used.

Try this approach in the editor

Approach 2: Optimized Approach with Skip for Non-Palindrome Primes

This approach skips checking numbers that cannot be palindromes. Recognizing that a number with an even number of digits cannot be a prime palindrome (except for 11), we avoid such unnecessary palindrome checks.

Also, leveraging specific palindrome generation techniques, such as half-length mirroring, enhances the efficiency instead of linearly checking each number for palindrome property.

Python

def is_prime(x):
    if x < 2:
        return False
    if x in (2, 3):
        return True
    if x % 2 == 0 or x % 3 == 0:
        return False
    i = 5
    while i * i <= x:
        if x % i == 0 or x % (i + 2) == 0:
            return False
        i += 6
    return True

def generate_palindrome(length, odd):
    if odd:
        start, end = 10**(length-1), 10**length
    else:
        start, end = 10**(length//2 - 1), 10**(length//2)
    for i in range(start, end):
        mid = str(i)
        if odd:
            yield int(mid + mid[-2::-1])  # create palindrome
        else:
            yield int(mid + mid[::-1])

def smallest_prime_palindrome(n):
    if n <= 2:
        return 2
    for length in range(len(str(n)), 10):  # limit length
        for odd in (True, False):  # switch between odd/even middle
            for palindrome in generate_palindrome(length, odd):
                if palindrome >= n and is_prime(palindrome):
                    return palindrome

Java

import java.util.*;

public class Solution {
    private boolean isPrime(int x) {
        if (x < 2) return false;
        if (x == 2) return true;
        if (x % 2 == 0) return false;
        for (int i = 3; i * i <= x; i += 2) {
            if (x % i == 0) return false;
        }
        return true;
    }

    public int smallestPrimePalindrome(int n) {
        if (n <= 2) return 2;
        int length = Integer.toString(n).length();
        while (true) {
            for (int odd = 0; odd < 2; ++odd) {
                int start = (int) Math.pow(10, (length + odd) / 2 - 1);
                int end = (int) Math.pow(10, (length + odd) / 2);
                for (int i = start; i < end; ++i) {
                    StringBuilder firstHalf = new StringBuilder(Integer.toString(i));
                    String fullPalindrome = firstHalf.toString() + new StringBuilder(firstHalf.substring(0, odd == 0 ? firstHalf.length() : firstHalf.length()-1)).reverse().toString();
                    int candidate = Integer.parseInt(fullPalindrome);
                    if (candidate >= n && isPrime(candidate)) return candidate;
                }
            }
            length++;
        }
    }
}

C++

#include <iostream>
#include <cmath>
#include <string>

bool is_prime(int x) {
    if (x < 2) return false;
    if (x == 2) return true;
    if (x % 2 == 0) return false;
    for (int i = 3; i * i <= x; i += 2) {
        if (x % i == 0) return false;
    }
    return true;
}

int smallest_prime_palindrome(int n) {
    if (n <= 2) return 2;
    int length = std::to_string(n).length();
    while (true) {
        for (int odd = 0; odd < 2; ++odd) {
            int start = pow(10, (length + odd) / 2 - 1);
            int end = pow(10, (length + odd) / 2);
            for (int i = start; i < end; ++i) {
                std::string first_half = std::to_string(i);
                std::string full_palindrome = odd ? first_half + std::string(first_half.rbegin() + 1, first_half.rend()) : first_half + std::string(first_half.rbegin(), first_half.rend());
                int candidate = std::stoi(full_palindrome);
                if (candidate >= n && is_prime(candidate)) return candidate;
            }
        }
        length++;
    }
}

JavaScript

function isPrime(x) {
    if (x < 2) return false;
    if (x === 2) return true;
    if (x % 2 === 0) return false;
    for (let i = 3; i * i <= x; i += 2) {
        if (x % i === 0) return false;
    }
    return true;
}

function smallestPrimePalindrome(n) {
    if (n <= 2) return 2;
    let length = n.toString().length;
    while (true) {
        for (let odd = 0; odd < 2; odd++) {
            const start = Math.pow(10, Math.floor((length + odd) / 2) - 1);
            const end = Math.pow(10, Math.floor((length + odd) / 2));
            for (let i = start; i < end; i++) {
                const firstHalf = i.toString();
                const fullPalindromeString = odd === 1 ? firstHalf + firstHalf.slice(0, -1).split('').reverse().join('') : firstHalf + firstHalf.split('').reverse().join('');
                const candidate = parseInt(fullPalindromeString, 10);
                if (candidate >= n && isPrime(candidate)) return candidate;
            }
        }
        length++;
    }
}

using System;

public class Solution {
    private static bool IsPrime(int x) {
        if (x < 2) return false;
        if (x == 2) return true;
        if (x % 2 == 0) return false;
        for (int i = 3; i * i <= x; i += 2) {
            if (x % i == 0) return false;
        }
        return true;
    }

    public int SmallestPrimePalindrome(int n) {
        if (n <= 2) return 2;
        int length = n.ToString().Length;
        while (true) {
            for (int odd = 0; odd < 2; ++odd) {
                int start = (int)Math.Pow(10, (length + odd) / 2 - 1);
                int end = (int)Math.Pow(10, (length + odd) / 2);
                for (int i = start; i < end; ++i) {
                    string firstHalf = i.ToString();
                    string fullPalindrome = odd == 1 ? firstHalf + Reverse(firstHalf.Substring(0, firstHalf.Length - 1)) : firstHalf + Reverse(firstHalf);
                    int candidate = int.Parse(fullPalindrome);
                    if (candidate >= n && IsPrime(candidate)) return candidate;
                }
            }
            length++;
        }
    }

    private string Reverse(string s) {
        char[] charArray = s.ToCharArray();
        Array.Reverse(charArray);
        return new string(charArray);
    }
}

This solution focuses on generating palindromes rather than checking every number. The generate_palindrome function creates palindromes based on mirrored half-values for both odd and even centered structures. For each potential palindrome, the primality is validated.

Complexity

Time complexity: Improved to O(nlogn) for palindromes and O(sqrt(n)) for specific number primes, significantly reducing checked numbers.
Space complexity: O(1) on storage structures for checks.

Try this approach in the editor

Approach 3: Default Approach

func primePalindrome(n int) int {
	isPrime := func(x int) bool {
		if x < 2 {
			return false
		}
		for v := 2; v*v <= x; v++ {
			if x%v == 0 {
				return false
			}
		}
		return true
	}

	reverse := func(x int) int {
		res := 0
		for x != 0 {
			res = res*10 + x%10
			x /= 10
		}
		return res
	}
	for {
		if reverse(n) == n && isPrime(n) {
			return n
		}
		if n > 10000000 && n < 100000000 {
			n = 100000000
		}
		n++
	}
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Brute Force Approach	Time complexity: Generally O(n * sqrt(n)), because for each number until the next prime palindrome, we may need to check its primality which takes sqrt(n) time. Space complexity: O(1), as no additional data structures are used.
Optimized Approach with Skip for Non-Palindrome Primes	Time complexity: Improved to O(nlogn) for palindromes and O(sqrt(n)) for specific number primes, significantly reducing checked numbers. Space complexity: O(1) on storage structures for checks.
Default Approach	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Search	O(k * sqrt(n))	O(1)	Good for understanding the problem or when n is small
Generate Palindromes + Prime Check	~O(P * sqrt(P))	O(1)	Preferred for interviews and large inputs since it skips non-palindrome numbers

Frequently asked questions

Is Prime Palindrome easy or hard?

Prime Palindrome is typically considered a medium-level problem. The brute force idea is simple, but the optimized solution requires recognizing that even-length palindromes greater than 11 cannot be prime and generating palindrome candidates efficiently.

How to solve Prime Palindrome efficiently?

Generate palindromes instead of checking every integer. Build odd-length palindromes by mirroring the first half of the number, then run a primality test using trial division up to sqrt(x). Skip even-length palindromes larger than 11 because they are always divisible by 11.

What is the best approach for Prime Palindrome?

The most efficient approach generates palindrome numbers directly and then checks if they are prime. Instead of scanning every integer, you construct palindromes by mirroring digits and run a primality test on each candidate. Skipping even-length palindromes (except 11) further reduces the search space.

Is Prime Palindrome asked at Google/Amazon/Meta?

Prime Palindrome represents the type of number theory and math-heavy question sometimes seen in interviews at companies like Google or Amazon. It tests knowledge of palindrome construction, prime testing, and optimization through mathematical observations.

What data structure is used in Prime Palindrome?

The problem mainly relies on mathematical operations rather than complex data structures. String manipulation or integer digit operations are used to construct and check palindromes, while a simple loop performs the primality test.

What is the time complexity of Prime Palindrome?

The brute force method runs in roughly O(k * sqrt(n)) because each candidate number requires a primality test up to sqrt(n). The optimized approach generates only palindrome candidates and checks primality, giving an effective complexity around O(P * sqrt(P)), where P is the candidate palindrome size.

Prime Palindrome Python or Java solution approach?

Most Python or Java solutions generate palindrome candidates and then verify primality with a sqrt-based check. This avoids iterating through every integer and significantly improves performance compared with brute force scanning.

Prime Palindrome solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Optimized Approach with Skip for Non-Palindrome Primes

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Prime Palindrome solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Optimized Approach with Skip for Non-Palindrome Primes

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems