Pretty much like #564 "Find the Closest Palindrome" | 277ms 100%
\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nThe key is to optimize the way to find the nearest palindrome at both sides of th
![Untitled.png](https://assets.leetcode.com/users/images/ba11d320-2973-43e8-98d6-ac599caaa27f_1703367784.3568902.png)\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe key is to optimize the way to find the nearest palindrome at both sides of the median. For further details, here is the link to a similar problem:\n https://leetcode.com/problems/find-the-closest-palindrome/\n\n\n# Approach\n1. Sort the given list\n2. Find the median\n3. Check if the median is a palindrome\n    - if yes, calculate the sum of absolute differences between the median and the rest of the list and return the result. Done !\n    - if not, proceeds to the next step\n4. Find the closest palindrome on both sides of the median\n    - you can do it by incrementing the median first positively then negatively, it\'s kinda slow if the value is huge\n    - for better approaches, see the link above for inspiration\n5. Calculate the sum of absolute differences between either of the two palindromes and each element on the list, compare both results and pick the smaller value.\n\n# Complexity\n- Time complexity:\nO(n*log(n))\n\n- Space complexity:\nO(n)\n\n# Code\n```\n\'\'\'superjinn 23-12-23\'\'\'\nclass Solution:\n    def minimumCost(self, nums):\n\n        def getP(N):\n            L = len(sn := str(N))\n            pool = [10 ** x + y for x, y in ((L - 1, -1), (L, 1))]\n            prefix = int(sn[:(L + 1) // 2])\n            for dx in [-1, 0, 1]:\n                temp = str(prefix + dx)\n                pool.append(int(temp + temp[-1 - (L & 1) :: -1]))\n            \n            pool.sort()\n            idx = bisect.bisect_right(pool, N)\n            return [pool[idx - 1], pool[idx]]\n\n        nums.sort()\n        mid = (L := len(nums)) // 2\n        median = nums[mid] if L & 1 else (nums[mid - 1] + nums[mid]) // 2\n        palins = [median] if (smed := str(median)) == smed[::-1] else getP(median)\n        \n        ans = math.inf\n        total = sum(nums)\n        pointer = preSum = 0\n        for P in palins:\n            while pointer < L and nums[pointer] < P:\n                preSum += nums[pointer]\n                pointer += 1\n            temp = P * (pointer * 2 - L) + total - preSum * 2\n            ans = min(ans, temp)\n\n        return ans\n```
['Math', 'Python3']