Find the Closest Palindrome

Find the Closest Palindrome looks like a search problem but is really a case analysis. The closest palindrome is never far away — it always comes from nudging the first half of the number, so we only ever build a handful of candidates and compare.

The slow way first

The brute force is to walk outward from n — check n+1, n-1, n+2, n-2, … and stop at the first palindrome. That is correct but can be hopeless: for a number like 10000000000000000 the nearest palindrome can be billions of steps away. We need to jump straight to the candidates instead of crawling.

The question to ask: what actually controls a palindrome? Only its first half. The back half is forced to mirror the front. So changing the answer means changing the prefix — and the closest palindromes come from the smallest possible prefix changes.

The idea: mirror the prefix, then nudge

Take the first half of n (the prefix) and mirror it to build a palindrome. The closest palindrome is one of just five candidates:

• mirror(prefix) — same prefix, mirrored.
• mirror(prefix + 1) — the next palindrome up.
• mirror(prefix - 1) — the next palindrome down.
• 99…9 with one fewer digit — handles cases like 1000 → 999.
• 10…01 with one more digit — handles cases like 99 → 101.

The key insight: drop n itself from the set (we need a different palindrome), then pick the candidate with the smallest distance, breaking ties toward the smaller value.

Walk through it

Step through the animation. We split 1283 into the prefix 12, mirror it to 1221, then build 1331 (prefix + 1) and 1111 (prefix − 1). We also add the boundary palindromes 99 and 10001. Scoring every distance, 1331 is only 48 away and wins.

Pseudocode

prefix = first half of n (round up the middle digit)
candidates = {}
add mirror(prefix)            # same prefix
add mirror(prefix + 1)        # one palindrome up
add mirror(prefix - 1)        # one palindrome down
add 99..9 with one fewer digit   # length shrinks
add 10..01 with one more digit   # length grows
remove n itself from candidates
return the candidate with smallest |candidate - n|, ties -> smaller value

The Python solution

def closest_palindrome(n: str) -> str:
    length = len(n)
    prefix = int(n[: (length + 1) // 2])
    def mirror(p):
        s = str(p)
        return int(s + s[length % 2:][::-1])
    cands = {mirror(prefix)}
    cands.add(mirror(prefix + 1))
    cands.add(mirror(prefix - 1))
    cands.add(10 ** (length - 1) - 1)
    cands.add(10 ** length + 1)
    cands.discard(int(n))
    best = min(cands, key=lambda c: (abs(c - int(n)), c))
    return str(best)

• prefix is the first half of n, taking the middle digit when the length is odd ((length + 1) // 2).
• mirror(p) reflects the prefix; s[length % 2:] skips the middle digit on odd lengths so it is not duplicated.
• We collect the three prefix-based palindromes plus the two length-boundary palindromes (99…9 and 10…01).
• cands.discard(int(n)) removes n itself — the answer must be a different palindrome.
• The min key (abs(c - int(n)), c) picks the closest candidate and, on a tie, the smaller value.

Complexity

We never search the number line — we construct the only candidates that can win. Building each is linear in the digit count, and there are a fixed five of them.

When this pattern shows up

Practice