Prime Palindrome

Medium
1282.

Prime Palindrome

Prime Palindrome is a medium coding problem on math and number theory, asked in Amazon and Microsoft interviews.

Return the smallest integer that is at least n and is both prime and a palindrome.

A prime has exactly two divisors, 1 and itself (so 1 is not prime). A palindrome reads the same forwards and backwards in base 10, like 101 or 7.

The answer is guaranteed to exist and to be at most 2 * 10^8.

Example 1

Input
n = 6
Output
7

Example 2

Input
n = 8
Output
11

Example 3

Input
n = 13
Output
101
Explanation
There is no prime palindrome between 13 and 100.

Constraints

  • 1 <= n <= 10^8
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var primePalindrome = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Prime Palindrome — Solution in Python, Java & C++

Prime Palindrome solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Prime Palindrome is a medium coding problem on math and number theory, asked in Amazon and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Math, Number Theory
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Return the smallest integer that is at least n and is both prime and a palindrome.

A prime has exactly two divisors, 1 and itself (so 1 is not prime). A palindrome reads the same forwards and backwards in base 10, like 101 or 7.

The answer is guaranteed to exist and to be at most 2 * 10^8.

Example 1

Input: n = 6
Output: 7

Example 2

Input: n = 8
Output: 11

Example 3

Input: n = 13
Output: 101
Explanation: There is no prime palindrome between 13 and 100.

Constraints

  • 1 <= n <= 10^8

Hints for Prime Palindrome

  1. Hint 1

    Walking upwards from n and testing every number is far too slow near 10^7: there is no 8-digit prime palindrome at all.

  2. Hint 2

    Every palindrome with an even number of digits is divisible by 11. So apart from 11 itself, only odd-length palindromes matter.

  3. Hint 3

    Generate odd-length palindromes in increasing order from their first half (the 'root'): root 123 gives 12321, and increasing roots give increasing palindromes. Start from the right root length and test primality only for palindromes ≥ n.

How to solve Prime Palindrome

Generate only odd-length palindromes, in increasing order, from their left halves; even-length palindromes are multiples of 11, so 11 is the only even-length answer.

Approach

  1. If 8 <= n <= 11, return 11.
  2. Let d be the number of digits of n and half = d/2 + 1 (integer division): the root length of the shortest odd-length palindromes that can reach n.
  3. If d is odd, start the root at the first half digits of n; otherwise at 10^(half-1).
  4. For each root in increasing order, mirror it (the root followed by its reverse without the last digit). If the palindrome is ≥ n and passes trial-division primality, return it.

Why it works

Alternating-digit sums show a palindrome with an even number of digits is divisible by 11, so none except 11 is prime. Mirroring is monotone — a larger root of the same length gives a larger palindrome, and the smallest palindrome of the next length beats the largest of this one — so scanning roots upward visits odd-length palindromes in increasing order and the first prime one that is ≥ n is the answer. Starting at the first half of n skips only roots whose palindromes are smaller than n. Single-digit inputs are covered by the one-digit roots, which are the palindromes 1 … 9.

Complexity

  • Time — O(R · √A): R roots tried (a few thousand at most) and √A per primality test of an answer-sized number
  • Space — O(1)

Pitfalls

  • Searching upwards from 9,989,900 one number at a time runs about 90 million steps before reaching 100,030,001.
  • Skipping even lengths drops 11 — handle n from 8 to 11 explicitly.
  • 1 is a palindrome but not a prime; n = 1 must return 2.

Reference solution

Python

def primePalindrome(n: int) -> int:
    def is_prime(x: int) -> bool:
        if x < 2:
            return False
        if x % 2 == 0:
            return x == 2
        d = 3
        while d * d <= x:
            if x % d == 0:
                return False
            d += 2
        return True

    if 8 <= n <= 11:
        return 11
    digits = len(str(n))
    half = digits // 2 + 1
    root = 10 ** (half - 1)
    if digits % 2 == 1:
        root = n // 10 ** (half - 1)
    while True:
        s = str(root)
        pal = int(s + s[-2::-1])
        if pal >= n and is_prime(pal):
            return pal
        root += 1

Java

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

public static int primePalindrome(int n) {
    if (n >= 8 && n <= 11) return 11;
    int digits = String.valueOf(n).length();
    int half = digits / 2 + 1;
    int scale = 1;
    for (int i = 1; i < half; i++) scale *= 10;
    int root = digits % 2 == 1 ? n / scale : scale;
    while (true) {
        int pal = root, t = root / 10;
        while (t > 0) {
            pal = pal * 10 + t % 10;
            t /= 10;
        }
        if (pal >= n && ppIsPrime(pal)) return pal;
        root++;
    }
}

C++

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

int primePalindrome(int n) {
    if (n >= 8 && n <= 11) return 11;
    int digits = to_string(n).size();
    int half = digits / 2 + 1;
    int scale = 1;
    for (int i = 1; i < half; i++) scale *= 10;
    int root = digits % 2 == 1 ? n / scale : scale;
    while (true) {
        int pal = root, t = root / 10;
        while (t > 0) {
            pal = pal * 10 + t % 10;
            t /= 10;
        }
        if (pal >= n && ppIsPrime(pal)) return pal;
        root++;
    }
}

JavaScript

var primePalindrome = function(n) {
    var isPrime = function(x) {
        if (x < 2) return false;
        if (x % 2 === 0) return x === 2;
        for (var d = 3; d * d <= x; d += 2) if (x % d === 0) return false;
        return true;
    };
    if (n >= 8 && n <= 11) return 11;
    var digits = String(n).length;
    var half = Math.floor(digits / 2) + 1;
    var root = Math.pow(10, half - 1);
    if (digits % 2 === 1) root = Math.floor(n / Math.pow(10, half - 1));
    for (;; root++) {
        var pal = root, t = Math.floor(root / 10);
        while (t > 0) {
            pal = pal * 10 + t % 10;
            t = Math.floor(t / 10);
        }
        if (pal >= n && isPrime(pal)) return pal;
    }
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue