Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Move from brute-force thinking to an efficient approach using math strategy.
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.
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.
101 and 12321 are palindromes.The test cases are generated so that the answer always exists and is in the range [2, 2 * 108].
Example 1:
Input: n = 6 Output: 7
Example 2:
Input: n = 8 Output: 11
Example 3:
Input: n = 13 Output: 101
Constraints:
1 <= n <= 108Problem summary: 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 * 108].
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math
6
8
13
sum-of-k-mirror-numbers)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #866: Prime Palindrome
class Solution {
public int primePalindrome(int n) {
while (true) {
if (reverse(n) == n && isPrime(n)) {
return n;
}
if (n > 10000000 && n < 100000000) {
n = 100000000;
}
++n;
}
}
private boolean isPrime(int x) {
if (x < 2) {
return false;
}
for (int v = 2; v * v <= x; ++v) {
if (x % v == 0) {
return false;
}
}
return true;
}
private int reverse(int x) {
int res = 0;
while (x != 0) {
res = res * 10 + x % 10;
x /= 10;
}
return res;
}
}
// Accepted solution for LeetCode #866: Prime Palindrome
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++
}
}
# Accepted solution for LeetCode #866: Prime Palindrome
class Solution:
def primePalindrome(self, n: int) -> int:
def is_prime(x):
if x < 2:
return False
v = 2
while v * v <= x:
if x % v == 0:
return False
v += 1
return True
def reverse(x):
res = 0
while x:
res = res * 10 + x % 10
x //= 10
return res
while 1:
if reverse(n) == n and is_prime(n):
return n
if 10**7 < n < 10**8:
n = 10**8
n += 1
// Accepted solution for LeetCode #866: Prime Palindrome
struct Solution;
impl Solution {
fn prime_palindrome(n: i32) -> i32 {
if (8..=11).contains(&n) {
return 11;
}
for i in 1..100_000 {
let mut x: Vec<char> = format!("{}", i).chars().collect();
let mut y = x.clone();
y.reverse();
x.extend(y.iter().skip(1));
let s: String = x.iter().collect();
let v = s.parse::<i32>().unwrap();
if v < n {
continue;
}
if Self::is_prime(v) {
return v;
}
}
0
}
fn is_prime(x: i32) -> bool {
if x < 2 || x % 2 == 0 {
return x == 2;
}
let mut i = 3;
while i * i <= x {
if x % i == 0 {
return false;
} else {
i += 2;
}
}
true
}
}
#[test]
fn test() {
let n = 6;
let res = 7;
assert_eq!(Solution::prime_palindrome(n), res);
let n = 8;
let res = 11;
assert_eq!(Solution::prime_palindrome(n), res);
let n = 13;
let res = 101;
assert_eq!(Solution::prime_palindrome(n), res);
let n = 9_989_900;
let res = 100_030_001;
assert_eq!(Solution::prime_palindrome(n), res);
}
// Accepted solution for LeetCode #866: Prime Palindrome
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #866: Prime Palindrome
// class Solution {
// public int primePalindrome(int n) {
// while (true) {
// if (reverse(n) == n && isPrime(n)) {
// return n;
// }
// if (n > 10000000 && n < 100000000) {
// n = 100000000;
// }
// ++n;
// }
// }
//
// private boolean isPrime(int x) {
// if (x < 2) {
// return false;
// }
// for (int v = 2; v * v <= x; ++v) {
// if (x % v == 0) {
// return false;
// }
// }
// return true;
// }
//
// private int reverse(int x) {
// int res = 0;
// while (x != 0) {
// res = res * 10 + x % 10;
// x /= 10;
// }
// return res;
// }
// }
Use this to step through a reusable interview workflow for this problem.
Simulate the process step by step — multiply n times, check each number up to n, or iterate through all possibilities. Each step is O(1), but doing it n times gives O(n). No extra space needed since we just track running state.
Math problems often have a closed-form or O(log n) solution hidden behind an O(n) simulation. Modular arithmetic, fast exponentiation (repeated squaring), GCD (Euclidean algorithm), and number theory properties can dramatically reduce complexity.
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.