Find the Closest Palindrome

hard math string

Problem

Given an integer string n, return the closest palindrome (different from n) by absolute value; tie → smaller.

Inputn = "123"

Output"121"

Candidates from prefix ±1, plus boundary palindromes for length transitions.

n (digits)

def nearest_palindromic(n):
    L = len(n); half = n[:(L + 1) // 2]
    cands = set()
    cands.add(10**(L - 1) - 1)  # all 9s of L-1
    cands.add(10**L + 1)         # 10...01 of L+1
    for d in (-1, 0, 1):
        h = str(int(half) + d)
        if not h or int(h) == 0: continue
        rev = h[:-1][::-1] if L % 2 else h[::-1]
        cands.add(int(h + rev))
    cands.discard(int(n))
    return str(min(cands, key=lambda x: (abs(x - int(n)), x)))

function nearestPalindromic(n) {
  const L = n.length, half = n.slice(0, (L + 1) >> 1);
  const cands = new Set();
  cands.add(BigInt(10) ** BigInt(L - 1) - 1n);
  cands.add(BigInt(10) ** BigInt(L) + 1n);
  for (const d of [-1n, 0n, 1n]) {
    const h = (BigInt(half) + d).toString();
    if (h === "0" || h === "") continue;
    const rev = (L % 2 ? h.slice(0, -1) : h).split("").reverse().join("");
    cands.add(BigInt(h + rev));
  }
  cands.delete(BigInt(n));
  let best = null, bestDiff = null;
  const N = BigInt(n);
  for (const c of cands) {
    const d = c > N ? c - N : N - c;
    if (best === null || d < bestDiff || (d === bestDiff && c < best)) { best = c; bestDiff = d; }
  }
  return best.toString();
}

class Solution {
    public String nearestPalindromic(String n) {
        int L = n.length();
        String half = n.substring(0, (L + 1) / 2);
        Set cands = new HashSet<>();
        cands.add((long) Math.pow(10, L - 1) - 1);
        cands.add((long) Math.pow(10, L) + 1);
        long N = Long.parseLong(n);
        for (int d = -1; d <= 1; d++) {
            long h = Long.parseLong(half) + d;
            if (h == 0) continue;
            String hs = String.valueOf(h);
            String rev = L % 2 == 1 ? hs.substring(0, hs.length() - 1) : hs;
            cands.add(Long.parseLong(hs + new StringBuilder(rev).reverse().toString()));
        }
        cands.remove(N);
        long best = -1, bestDiff = Long.MAX_VALUE;
        for (long c : cands) {
            long diff = Math.abs(c - N);
            if (diff < bestDiff || (diff == bestDiff && c < best)) { best = c; bestDiff = diff; }
        }
        return String.valueOf(best);
    }
}

string nearestPalindromic(string n) {
    int L = n.size();
    string half = n.substr(0, (L + 1) / 2);
    set cands;
    cands.insert((long long) pow(10, L - 1) - 1);
    cands.insert((long long) pow(10, L) + 1);
    long long N = stoll(n);
    for (int d = -1; d <= 1; d++) {
        long long h = stoll(half) + d;
        if (h == 0) continue;
        string hs = to_string(h);
        string rev = L % 2 == 1 ? hs.substr(0, hs.size() - 1) : hs;
        reverse(rev.begin(), rev.end());
        cands.insert(stoll(hs + rev));
    }
    cands.erase(N);
    long long best = -1, bestDiff = LLONG_MAX;
    for (long long c : cands) {
        long long diff = abs(c - N);
        if (diff < bestDiff || (diff == bestDiff && c < best)) { best = c; bestDiff = diff; }
    }
    return to_string(best);
}

Explanation

Instead of scanning numbers near n one by one (far too slow for big inputs), we realize the closest palindrome must come from a tiny set of candidates. We build that set and pick the nearest.

The key idea is the prefix mirror: a palindrome is decided by its first half. Taking half = n[:(L+1)//2] and mirroring it gives a palindrome close to n. But the nearest one might use the prefix slightly changed, so we try the half +1, +0, and -1 and mirror each.

Two extra boundary candidates handle digit-length changes: 10^(L-1) - 1 (a row of nines like 99 or 999, the largest shorter palindrome) and 10^L + 1 (like 1001, the smallest longer one). These cover cases like 1000 or 999.

We drop n itself from the set (the answer must differ), then choose the candidate with the smallest abs(x - n), breaking ties by picking the smaller number via the key (abs(x - int(n)), x).

Example: "123". Mirroring the prefix gives 121 (Δ=2) and 131 (Δ=8); boundaries give 99 and 1001. The closest is 121.

Time: O(L) Space: O(1)