Find the Closest Palindrome: Mirror Prefixes and Handle Digit-Length Boundaries

Construct a bounded set of mirrored candidates to find the closest palindrome without scanning neighboring integers. Mirror the current left prefix and its immediate predecessor and successor, then add the shorter all-nines boundary and the next-length one-zeroes-one boundary. Remove the input itself and compare candidates by absolute distance, then numeric value.

The official Closest Palindrome statement requires excluding the input and returning the smaller palindrome on a tie, for positive inputs of up to eighteen digits. The proof, original boundary trace, implementation, and tests below are original. Find next and closest palindromes is candidate-reported practice that distinguishes closest from strictly next-greater output.

Choose the numeric objective before mirroring

Use canonical decimal notation: a palindrome reads identically forward and backward without a leading-zero representation. The answer minimizes numeric absolute difference from the input, with the input itself excluded. A larger palindrome is not automatically preferable, and a smaller one is not automatically closer.

When two candidates are equally distant, return the numerically smaller one. A comparison key of (distance,value) represents that rule directly. Relying on set iteration order or whichever candidate was inserted first makes tie behavior accidental.

The official input is a positive decimal integer string without leading zeros. Zero can be an answer, as for input one. Negative signs and fixed-width digit strings are outside this contract; reversing a padded representation such as 00100 answers a different formatting question.

A closest-palindrome search must consider smaller candidates as well as the next larger palindrome. For input one thousand, one thousand one is next-greater, but nine hundred ninety-nine is equally close and wins the closest-palindrome tie rule.

Let the left prefix determine a same-length palindrome

For D digits, the first ceiling(D/2) digits determine the mirror. In an odd-length number, the final prefix digit is the middle and must not be duplicated when mirroring. In an even-length number, mirror the entire prefix.

With four digits, prefix twelve mirrors to 1221. Prefix one-twenty-three determines odd-length palindrome twelve-three-twenty-one when D is five. The middle three appears once.

At a fixed length, increasing the determining prefix increases the palindrome. The leading differing digit dominates everything to its right. This monotone order is what permits a small neighboring-prefix candidate set.

The numeric value formed by simply mirroring the current prefix can lie below, above, or exactly at the input. Mirroring alone is therefore only one candidate, not a complete solution.

Generate the neighboring prefixes

Let P be the determining prefix of the input. Construct mirrors for P minus one, P, and P plus one. The current-prefix mirror is the only palindrome with that prefix. Among smaller prefixes, the closest possible same-length palindrome uses the immediate smaller prefix; any still smaller prefix produces a smaller value farther from the input.

The symmetric argument applies above the current prefix. Thus no same-length palindrome with a prefix two or more steps away can beat all three candidates. This argument concerns ordered numeric intervals, not a guess that palindromes are usually close.

When the prefix loses or gains a digit, the naive mirror may no longer have the original length. The implementation tolerates extra valid palindrome candidates, while explicit length boundaries ensure the important cross-length answers are included.

A fixed-width translation can instead skip mirrors whose prefix width changes and handle them exclusively through the boundary candidates. Either implementation must account for the transition deliberately.

Add both digit-length boundaries

The largest palindrome with fewer than D digits is 10^(D-1)-1, an all-nines value. It is the closest shorter-length candidate because every other shorter nonnegative value is no larger.

The smallest palindrome with more than D digits is 10^D+1. It starts and ends with one and contains zeroes between them. A larger-length positive palindrome cannot be smaller without either a leading zero or a zero final digit inconsistent with its leading one.

For D one, the shorter boundary is zero. For a lower bound near a power of ten, the shorter all-nines candidate is essential. For an all-nines input, the next-length candidate handles the carry across the entire digit string.

These boundaries are not permission to return the input itself. An input can already be palindromic, so exclude its numeric value after all candidates have been collected.

Trace an original boundary and tie case

Take input 1000. Its length is four and its determining prefix is ten. The useful cross-length candidates include nine hundred ninety-nine and one thousand one.

The two distance-one candidates tie, so return 999. A method that always increments and mirrors would incorrectly return 1001 for the closest objective even though it correctly solves the next-greater variant.

For input 99, exclude ninety-nine itself and compare the longer boundary one hundred one against smaller candidates. One hundred one is two away and wins. For 12321, the input's mirror is itself and must be removed; 12221 and 12421 are each one hundred away, so choose the smaller.

Implement candidate generation and comparison

def closest_palindrome(text):
    value=int(text)
    length=len(text)
    half=(length+1)//2
    prefix=int(text[:half])
    candidates={10**(length-1)-1,10**length+1}
    for following in (prefix-1,prefix,prefix+1):
        if following<0:
            continue
        left=str(following)
        right=left[:-1]if length%2 else left
        candidates.add(int(left+right[::-1]))
    candidates.discard(value)
    return str(min(candidates,key=lambda candidate:(abs(candidate-value),candidate)))

The set removes duplicate candidate values automatically. Duplicates are harmless for minimum selection, unlike occurrence-counting problems where deduplicating can change the answer. Here the result is one numeric value rather than a count of ways to construct it.

The odd-length branch removes the center from the part to be reversed. Reversing the entire odd prefix would duplicate the middle digit and produce the wrong length. The even branch mirrors every prefix digit.

Conversion through Python integers canonicalizes a generated zero string to zero and supports candidates larger than the input's width. The final result is converted back to an ordinary decimal string with no artificial leading zeros.

The code trusts the official positive, no-leading-zero input contract. A reusable library wrapper can validate it explicitly. Do not accept a negative sign or decimal point and expect the same slicing and prefix arithmetic to preserve meaning.

Prove the candidate set contains an optimum

Separate possible answers into shorter, same-length, and longer numbers. Within shorter numbers, the largest palindrome is nearest to the positive D-digit input. Within longer numbers, the smallest palindrome is nearest. The two boundary candidates cover those classes.

For same-length answers, prefixes below P are all below the input's prefix interval, and prefixes above P are all above it. The immediate neighboring prefix gives the nearest candidate on each respective side. Prefix P itself determines exactly one palindrome.

Therefore every possible palindrome is either explicitly included or no closer than an included candidate in its class. Removing the input leaves the nearest allowed alternatives. Minimizing the ordered pair of distance and value then enforces both the objective and tie rule.

A few extra valid palindromes caused by prefix-width changes cannot invalidate that reasoning. They compete under the same objective, while the argument already guarantees that a true optimum is present. They can, however, affect numeric-width requirements in a translation.

Protect intermediates as well as the returned answer

The official input has at most eighteen digits, so Python's integer conversion is small here. That does not justify converting a hypothetical hundred-thousand-digit extension to a bounded machine integer or claiming the same runtime behavior for arbitrary lengths.

There is a subtler fixed-width issue even under the official bound. Incrementing a nine-digit all-nines prefix creates ten digits. Naively mirroring that prefix for an even eighteen-digit input can create a twenty-digit extra candidate, although the useful next-length answer has only nineteen digits.

Thus a result that fits a signed sixty-four-bit type does not prove every naive candidate also fits. Use wider arithmetic, string-based comparison, or the prefix-width filter plus explicit boundaries. Python's arbitrary-precision integers make the displayed extra candidate safe.

Do not compare decimal strings lexicographically without considering length. 999 sorts after 1001 as ordinary text but represents the smaller number. The implementation uses numeric comparisons under its bounded-length contract.

Count work in terms of digit length

The candidate count is constant: at most three mirrors plus two boundaries before deduplication and input removal. Each constructed string contains O(D) digits, so character construction uses O(D) work and O(D) storage.

Arithmetic and conversion operate on D-digit integers. Under the official eighteen-digit bound they are small bounded operations. For an unbounded-digit analysis, include the implementation's big-integer conversion and subtraction costs rather than silently treating arbitrary-precision arithmetic as constant time.

An outward search that checks every integer until finding a palindrome has no comparable constant candidate bound. A long gap can make it perform many repeated decimal reversals. Candidate construction exploits the prefix order directly instead of hoping the nearest answer is only a few increments away.

If the task changes to a fixed-width palindrome or a decimal with a prescribed scale, revisit the representation and boundary proof. The canonical positive-integer length transitions above do not automatically cover padded strings or mirrored decimal points.

Check against an independently generated palindrome inventory

The saved local fixture enumerates palindromes from zero through two hundred thousand by checking their full decimal reversals. For each input from one through one hundred thousand, it searches that independent inventory for allowed neighbors and compares the distance-and-value minimum with the constructor.

This gives one hundred thousand finite local queries. Named cases include one, ten, eleven, ninety-nine, one thousand, nine hundred ninety-nine, 12321, and the eighteen-digit all-nines input. The last case checks a returned nineteen-digit boundary.

The inventory oracle does not generate palindromes by mirroring neighboring prefixes, so it can expose a shared mistake that two copies of the candidate algorithm would miss. Its finite range is chosen to contain the relevant neighbors for the tested query interval.

These checks do not establish a private judge result or an arbitrary-length string implementation. The class-by-length and prefix-order proofs support the general bounded contract. When a case fails, print each candidate with its numeric distance before changing the tie rule.

Diagnose exclusions before adding more candidates

If an already-palindromic input returns itself, inspect the explicit removal step. If one thousand returns one thousand one, inspect tie comparison rather than adding a wider prefix range.

If an all-nines input fails, inspect the next-length boundary and intermediate integer width. If odd-length candidates have an extra central digit, inspect which prefix portion is reversed.

A missing boundary should be repaired with its length-class argument. Increasing the prefix range until a few tests pass can obscure why only the nearest prefixes are necessary and can still miss a carry-related representation error.

Practice closest and next-greater contracts separately

These PracHub entries are candidate-reported practice material. Most ask for a next-greater palindrome or combine that task with validation; they do not all use the closest objective or smaller-value tie rule.

Use the closest follow-up in Find next and closest palindromes. Reproduce 1000 to 999 and 99 to 101, then explain which candidate handles each digit-length transition before writing a string-only translation.

Sources and Further Reading

• LeetCode 564: Find the Closest Palindrome: official input bound, exclusion, distance and tie rules.
• Python integer documentation: arbitrary-precision arithmetic used by this bounded-input implementation.
• Python bisect documentation: locating neighbors in the independent palindrome inventory.