Find the Closest Palindrome - Practice Coding Problems

Find the Closest Palindrome - Problem

Math String Hard

Given a string n representing an integer, return the closest integer (not including itself), which is a palindrome. If there is a tie, return the smaller one.

The closest is defined as the absolute difference minimized between two integers.

Input & Output

Example 1 — Basic Case

$ Input: n = "123"

› Output: "121"

💡 Note: The closest palindromes are 121 (distance 2) and 131 (distance 8). Since 121 is closer, we return "121".

Example 2 — Single Digit

$ Input: n = "1"

› Output: "0"

💡 Note: For single digit input, the closest palindrome is simply the digit minus 1 (except for 0 which returns 1).

Example 3 — Edge Case 99

$ Input: n = "99"

› Output: "101"

💡 Note: The candidates are 9 (distance 90) and 101 (distance 2). 101 is much closer, so return "101".

Constraints

1 ≤ n.length ≤ 18
n consists of only digits
n does not have leading zeros
n is representing an integer in the range [1, 10¹⁸ - 1]

Visualization

Tap to expand

Understanding the Visualization

Input

Given number as string (e.g., "123")

Generate

Create palindrome candidates mathematically

Compare

Return closest palindrome (prefer smaller if tie)

Key Takeaway

🎯 Key Insight: Only 5 palindrome candidates need to be checked for any number

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is that there are only 5 possible closest palindromes to any given number. The optimal approach mathematically generates these candidates: mirror the current prefix, increment/decrement the middle part and mirror, plus edge cases for different lengths. Time: O(n), Space: O(n) where n is the number of digits.

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Palindrome Generation	O(n)	O(n)	Generate only 5 possible closest palindrome candidates mathematically
Brute Force Search	O(n)	O(1)	Check numbers incrementally around the given number until finding palindromes

Mathematical Palindrome Generation — Algorithm Steps

Step 1: Handle special cases (single digit, all 9s, 10...01)
Step 2: Mirror left half to right half
Step 3: Try incrementing middle part and mirror
Step 4: Try decrementing middle part and mirror
Step 5: Compare all candidates and return closest

Visualization

Tap to expand

Step-by-Step Walkthrough

Extract

Get left half of input number

Generate

Create 5 palindrome candidates

Compare

Find closest to original

Code -

solution.c — C

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

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

void getPalindrome(char* prefix, int isOdd, char* result) {
    strcpy(result, prefix);
    char suffix[20];
    strcpy(suffix, prefix);
    reverse(suffix);
    if (isOdd) {
        strcat(result, suffix + 1);
    } else {
        strcat(result, suffix);
    }
}

char* solution(char* n) {
    int length = strlen(n);
    char* result = malloc(20);
    
    // Handle single digit
    if (length == 1) {
        int digit = atoi(n);
        if (digit == 0) {
            strcpy(result, "1");
            return result;
        }
        sprintf(result, "%d", digit - 1);
        return result;
    }
    
    char candidates[5][20];
    int candidateCount = 0;
    
    // Candidate 1: 999...999 (one digit less)
    for (int i = 0; i < length - 1; i++) {
        candidates[candidateCount][i] = '9';
    }
    candidates[candidateCount][length - 1] = '\0';
    candidateCount++;
    
    // Candidate 2: 100...001 (one digit more)
    candidates[candidateCount][0] = '1';
    for (int i = 1; i < length; i++) {
        candidates[candidateCount][i] = '0';
    }
    candidates[candidateCount][length] = '1';
    candidates[candidateCount][length + 1] = '\0';
    candidateCount++;
    
    // Get the middle part for mirroring
    int isOdd = length % 2;
    int midEnd = length / 2 + isOdd;
    char prefix[20];
    strncpy(prefix, n, midEnd);
    prefix[midEnd] = '\0';
    
    // Candidate 3: Mirror current prefix
    getPalindrome(prefix, isOdd, candidates[candidateCount]);
    if (strcmp(candidates[candidateCount], n) != 0) {
        candidateCount++;
    }
    
    // Find closest
    long long num = atoll(n);
    long long minDiff = LLONG_MAX;
    
    for (int i = 0; i < candidateCount; i++) {
        if (strcmp(candidates[i], n) != 0) {
            long long candidateNum = atoll(candidates[i]);
            long long diff = llabs(candidateNum - num);
            if (diff < minDiff || (diff == minDiff && candidateNum < atoll(result))) {
                minDiff = diff;
                strcpy(result, candidates[i]);
            }
        }
    }
    
    return result;
}

int main() {
    char n[20];
    fgets(n, sizeof(n), stdin);
    n[strcspn(n, "\n")] = 0;
    char* result = solution(n);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

String operations are O(n) where n is the number of digits, but we only generate 5 candidates

✓ Linear Growth

Space Complexity

O(n)

Store candidate strings and intermediate results

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~35 min Avg. Time

856 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

Mathematical Palindrome Generation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler