Find the Closest Palindrome

Find the Closest Palindrome

What is this problem about?

The Find the Closest Palindrome interview question is a challenging mathematical and string manipulation task. You are given a numeric string $n$, and you need to find the closest integer (excluding $n$ itself) that is a palindrome. If there is a tie between two palindromes (one larger and one smaller), you should return the smaller one.

Why is this asked in interviews?

Top companies like Google and Amazon ask the Find the Closest Palindrome coding problem to test a candidate's ability to handle extreme edge cases and large numbers. This is a "Hard" problem because you cannot simply increment/decrement the number to find the answer—the search space is too large. It evaluates your knowledge of Math interview patterns and digit-level manipulation.

Algorithmic pattern used

This problem follows the Candidate Generation pattern. The closest palindrome is usually derived from the first half of the input number.

1. Extract Half: Get the first $ceil(L/2)$ digits of $n$. Let this be $P$.
2. Generate 5 Candidates:

• Palindrome formed by $P$ mirrored.
• Palindrome formed by $(P+1)$ mirrored.
• Palindrome formed by $(P-1)$ mirrored.
• The "Lower Boundary" case: $10^{L-1} - 1$ (e.g., 999 for a 4-digit input).
• The "Upper Boundary" case: $10^L + 1$ (e.g., 10001 for a 4-digit input).

1. Find Best: Compare the absolute difference between each candidate and the original number.

Example explanation

Input $n = "123"$.

1. Half is "12".
2. Candidates:

• Mirror 12: "121"
• Mirror 13: "131"
• Mirror 11: "111"
• Boundary: 9, 99, 1001

1. Differences: $|121-123|=2$, $|131-123|=8$, $|111-123|=12$, $|99-123|=24$.
2. Closest is 121.

Common mistakes candidates make

• Integer Overflow: Forgetting that $n$ can have up to 18 digits, which exceeds standard 32-bit integers. Use long long or BigInt.
• Missing the Boundaries: Failing to consider numbers that change length (like 100 becoming 99 or 101).
• Ties: Returning the larger palindrome in a tie instead of the smaller one.

Interview preparation tip

When generating palindromes, always focus on the prefix. A palindrome is entirely determined by its first half. Changing digits at the center of the number has a much smaller impact on the overall value than changing digits at the ends.