Commented | Intuitive
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```python3 []\nclass Solution:\n    def minimumCost(self, nums: List[int]) -> int:\n        # other approaches:\n        # Generate all palindromes < 10 ^ 9: O(10 ^ 5)\n        # Find closest palindrome to x: O(logn)\n        # Find closest palidrome for all the n elements: O(NlogN)\n        # We can calculate cost by using prefix sums, for any palindrome we will find all the nums greater than the palindrome: O(logN).\n        # Total cost: O(NlogN)\n        # Complicated\n# old ----------------------------------------------------\n# better, why try n palindromes, just try 2, mean and median\n        nums.sort()\n        N = len(nums)\n        \n        def isPalindrome(s: str) -> bool:\n            n = len(s)\n            for i in range(n):\n                if s[i] != s[n - 1 - i]:\n                    return False\n            return True\n        \n        def getSmallerPalindrome(num: int) -> int:\n            for i in range(num, -1, -1):\n                if isPalindrome(str(i)):\n                    return i\n            return float(\'-inf\')\n\n        def getLargerPalindrome(num: int) -> int:\n            for i in range(num, 1000000001):\n                if isPalindrome(str(i)):\n                    return i\n            return float(\'-inf\')\n        \n        medians = [nums[N // 2], nums[N // 2 - 1]] if N % 2 == 0 else [nums[N // 2]]\n        ans = float(\'inf\')\n        for med in medians:\n            pal1, pal2 = getSmallerPalindrome(med), getLargerPalindrome(med)\n            cost1, cost2 = 0, 0\n            for num in nums:\n                cost1 += abs(num - pal1)\n                cost2 += abs(num - pal2)\n            ans = min(ans, cost1, cost2)\n        return ans\n```
['Python3']