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
Hint 1
Walking upwards from
nand testing every number is far too slow near 10^7: there is no 8-digit prime palindrome at all.Hint 2
Every palindrome with an even number of digits is divisible by 11. So apart from 11 itself, only odd-length palindromes matter.
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
- If
8 <= n <= 11, return 11. - Let
dbe the number of digits ofnandhalf = d/2 + 1(integer division): the root length of the shortest odd-length palindromes that can reachn. - If
dis odd, start the root at the firsthalfdigits ofn; otherwise at10^(half-1). - For each root in increasing order, mirror it (the root followed by its reverse without the last digit). If the palindrome is ≥
nand 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
nfrom 8 to 11 explicitly. - 1 is a palindrome but not a prime;
n = 1must 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 += 1Java
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.