Prime Palindrome - Practice Coding Problems

Prime Palindrome - 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⁸].

Input & Output

Example 1 — Small Number

$ Input: n = 9

› Output: 11

💡 Note: Starting from 9: 9 is palindrome but not prime (divisible by 3), 10 is not palindrome, 11 is both palindrome and prime (only divisible by 1 and 11)

Example 2 — Already Prime Palindrome

$ Input: n = 2

› Output: 2

💡 Note: 2 itself is both prime and palindrome, so return 2

Example 3 — Larger Input

$ Input: n = 13

› Output: 101

💡 Note: 13 is prime but not palindrome. Next palindromes are 22, 33, 44, etc. but they're not prime. 101 is the first prime palindrome ≥ 13

Constraints

1 ≤ n ≤ 2 × 10⁸
The answer always exists and is in the range [2, 2 × 10⁸]

Visualization

Tap to expand

Understanding the Visualization

Input

Given n = 9, find prime palindrome ≥ 9

Check Conditions

Number must be palindrome AND prime

Output

Return 11 (palindrome: 11, prime: only divisors are 1, 11)

Key Takeaway

🎯 Key Insight: Even-length palindromes (except 11) are divisible by 11, so focus on odd-length palindromes for efficiency

Asked in

G Google 15 F Facebook 10 a Amazon 8

The key insight is that even-length palindromes (except 11) are divisible by 11, so we focus on odd-length palindromes. The optimal approach generates palindrome candidates systematically rather than checking every number. Best approach: Generate palindromes by mirroring first half, then test primality. Time: O(√n × log n), Space: O(log n)

Common Approaches

Approach	Time	Space	Notes
✓ Generate Palindromes	O(√n × log n)	O(log n)	Generate palindrome candidates systematically, then check primality
Brute Force Check	O(n × √n)	O(1)	Check every number starting from n until we find a prime palindrome

Generate Palindromes — Algorithm Steps

Handle small cases (2, 3, 5, 7, 11)
Generate odd-length palindromes by mirroring first half
Check each palindrome candidate for primality
Return first prime palindrome found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create palindrome candidates by mirroring

Test

Check each candidate for primality

Result

Return first prime palindrome found

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int isPrime(int num) {
    if (num < 2) return 0;
    if (num == 2) return 1;
    if (num % 2 == 0) return 0;
    for (int i = 3; i * i <= num; i += 2) {
        if (num % i == 0) return 0;
    }
    return 1;
}

void reverseString(char* str, int len) {
    for (int i = 0; i < len / 2; i++) {
        char temp = str[i];
        str[i] = str[len - 1 - i];
        str[len - 1 - i] = temp;
    }
}

int solution(int n) {
    // Handle small cases
    if (n <= 2) return 2;
    if (n <= 3) return 3;
    if (n <= 5) return 5;
    if (n <= 7) return 7;
    if (n <= 11) return 11;
    
    char s[20];
    sprintf(s, "%d", n);
    int length = strlen(s);
    
    // Try current length if odd
    if (length % 2 == 1) {
        int mid = length / 2;
        char firstHalf[20];
        strncpy(firstHalf, s, mid + 1);
        firstHalf[mid + 1] = '\0';
        
        char reversed[20];
        strncpy(reversed, firstHalf, mid);
        reversed[mid] = '\0';
        reverseString(reversed, mid);
        
        char palindromeStr[40];
        strcpy(palindromeStr, firstHalf);
        strcat(palindromeStr, reversed);
        int palindrome = atoi(palindromeStr);
        
        if (palindrome >= n && isPrime(palindrome)) {
            return palindrome;
        }
        
        int firstHalfInt = atoi(firstHalf);
        sprintf(firstHalf, "%d", firstHalfInt + 1);
        if (strlen(firstHalf) == mid + 1) {
            strncpy(reversed, firstHalf, mid);
            reversed[mid] = '\0';
            reverseString(reversed, mid);
            strcpy(palindromeStr, firstHalf);
            strcat(palindromeStr, reversed);
            int nextPalindrome = atoi(palindromeStr);
            if (isPrime(nextPalindrome)) {
                return nextPalindrome;
            }
        }
    }
    
    // Try next odd length
    int nextLength = length % 2 == 0 ? length + 1 : length + 2;
    int firstHalfLen = nextLength / 2 + 1;
    char firstHalf[20] = "1";
    for (int i = 1; i < firstHalfLen; i++) {
        strcat(firstHalf, "0");
    }
    
    while (1) {
        char reversed[20];
        strncpy(reversed, firstHalf, firstHalfLen - 1);
        reversed[firstHalfLen - 1] = '\0';
        reverseString(reversed, firstHalfLen - 1);
        
        char palindromeStr[40];
        strcpy(palindromeStr, firstHalf);
        strcat(palindromeStr, reversed);
        int palindrome = atoi(palindromeStr);
        
        if (isPrime(palindrome)) {
            return palindrome;
        }
        
        int firstHalfInt = atoi(firstHalf);
        sprintf(firstHalf, "%d", firstHalfInt + 1);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", solution(n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(√n × log n)

Generate O(√n) palindrome candidates, each prime check takes O(√n) time

⚡ Linearithmic

Space Complexity

O(log n)

Space for string manipulation when constructing palindromes

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Generate Palindromes — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler