Given an integer n, find the closest integer (not including itself), which is a palindrome. 

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

Example 1:

Input: "123"
Output: "121"



Note:

The input n is a positive integer represented by string, whose length will not exceed 18.
If there is a tie, return the smaller one as answer.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Mathematics

Starter code:
class Solution:
    def nearestPalindromic(self, n: str) -> str:
        

Solutions:
class Solution:

	def nearestPalindromic(self, num):
		K = len(num)
		candidates = set([10 ** K + 1, 10 ** (K - 1) - 1])
		Prefix = int(num[:(K + 1) // 2])
		for start in map(str, [Prefix - 1, Prefix, Prefix + 1]):
			candidates.add(start + [start, start[:-1]][K & 1][::-1])
		candidates.discard(num)
		return str(min(candidates, key=lambda x: (abs(int(x) - int(num)), int(x))))


class Solution:

	def nearestPalindromic(self, n):
		K = len(n)
		candidates = [str(10 ** k + d) for k in (K - 1, K) for d in (-1, 1)]
		Prefix = int(n[:(K + 1) // 2])
		for start in map(str, [Prefix - 1, Prefix, Prefix + 1]):
			candidates.append(str(start) + (start[:-1] if K % 2 == 1 else start)[::-1])
		(ans, diff) = (0, float('inf'))
		base = int(n)
		for C in candidates:
			b = int(C)
			d = abs(b - base)
			if d == 0 or d > diff or (d == diff and b > ans):
				continue
			ans = int(C)
			diff = d
		return str(ans)


class Solution:

	def nearestPalindromic(self, n):
		K = len(n)
		candidates = [str(10 ** k + d) for k in (K - 1, K) for d in (-1, 1)]
		prefix = n[:(K + 1) // 2]
		P = int(prefix)
		for start in map(str, (P - 1, P, P + 1)):
			candidates.append(start + (start[:-1] if K % 2 else start)[::-1])

		def delta(x):
			return abs(int(n) - int(x))
		ans = None
		for cand in candidates:
			if cand != n and (not cand.startswith('00')):
				if ans is None or delta(cand) < delta(ans) or (delta(cand) == delta(ans) and int(cand) < int(ans)):
					ans = cand
		return ans


class Solution:

	def nearestPalindromic(self, n):
		evenPal = lambda sp: int(sp + sp[::-1])
		oddPal = lambda sp: int(sp + sp[::-1][1:])
		(sn, n) = (n, int(n))
		if len(sn) == 1:
			return str(n - 1)
		ans = -999999999999999999
		mid = len(sn) // 2
		for sp in (sn[:mid], sn[:mid + 1], str(int(sn[:mid]) * 10)):
			p = int(sp)
			for pal in (evenPal, oddPal):
				for d in (-1, 0, 1):
					val = pal(str(p + d))
					if val == n:
						continue
					ans = min(ans, val, key=lambda x: (abs(x - n), x))
		return str(ans)


class Solution:

	def getPalindromic(self, num, mid=''):
		return str(num) + mid + str(num)[::-1]

	def nearestPalindromic(self, n):
		if len(n) == 1:
			return str(int(n) - 1)
		midstr = '' if len(n) % 2 == 0 else n[len(n) // 2]
		midint = -1 if len(n) % 2 == 0 else int(n[len(n) // 2])
		s = [''] * 6
		s[0] = '9' * (len(n) - 1)
		s[1] = self.getPalindromic(int(n[:len(n) // 2]) - 1, midstr)
		s[2] = n[:len(n) // 2] + str(midint - 1) + n[:len(n) // 2][::-1] if midint > 0 else self.getPalindromic(int(n[:len(n) // 2]) - 1)
		s[3] = n[:len(n) // 2] + midstr + n[:len(n) // 2][::-1]
		s[4] = n[:len(n) // 2] + str(midint + 1) + n[:len(n) // 2][::-1] if midint < 10 and midint > -1 else self.getPalindromic(int(n[:len(n) // 2]) + 1)
		s[5] = '1' + '0' * (len(n) - 1) + '1'
		nums = map(lambda x: abs(int(x) - int(n)), s)
		nums = list(map(lambda x: x if x > 0 else 1e+18, nums))
		return s[nums.index(min(nums))]