Intuition and Mathematical Explanation. Improve your understanding!
Intuition\n Describe your first thoughts on how to solve this problem. \n\nClosest palindrome to the number x that minimizes our absolute sum is our answer. Thi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nClosest palindrome to the number x that minimizes our absolute sum is our answer. This deduction is easy to get. But what should the x be is the main problem.\n\nWhy median and not mean? The most common doubt that we have for the minimizing the sum of absolute differences.\nI had the same doubt. This [post](https://math.stackexchange.com/questions/113270/the-median-minimizes-the-sum-of-absolute-deviations-the-ell-1-norm) kind of cleared it out for me.\n\nShort explanation:\nSay we have 5 points named s1 ... s5. And x is the number that we want to find which minimizes this sum of absolute differences.\nVisualize the sum of absolute differences as distance between point x and the 5 points. Assume that s1 ... s5 is sorted.\n\n**Cases:**\n- If x is smaller than s1. Moving towards left side of the number line, the distance from all the point increases cause we are moving away from all the points.\n- If x is larger than s5. The same things applies as above if we move towards the right side.\n- We know that to minimize the sum we must lie between s1 and s5. \n    - Assume that we are at s1, if we move a small distance say y towards right, it means that distance from s1 increase by y but the rest of the distances decrease by y. Net effect: (+y -4y = -3y). Our sum is 3y times less than the previous one.\n    - Now, assume that we are at s2 and do the same thing. Here, distance from s1 and s2 would be increase by y times and for the rest of the points it would decrease. Net Effect: (-2y + 3y = -y). We are still observing the decrease in our sum respective to the previous sums.\n    - When we reach the median, the above effect stops. If we move any further. Now we would be increasing the sum as net distance increase (more numbers on the left rather than right).\n\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nI explained the above intuition but I lied. The answer is not actually the closest thing to median. This realization came through this test case\n109 113 115 122 128\nHere the median is 115. Closest palindrome to 115 is 111.\nSum of Absolute Diff: 3 + 2 + 4 + 11 + 17 = 36\nBut, sadly the answer is 121.\nSum of Absolute Diff: 12 + 8 + 6 + 1 + 7 = 34\n\nFrom this test case I realized that its actually not the closest palindrome to the median. But, its the closest two palindrome to the median on either sides. And the minimum sum of absolute differences taking these two as references is the answer.\n\nWhy the above logic works, think about it using the above presented mathematical reasoning. We don\'t know how distant the points are on either sides of the median. \n\nIf median is the palindrome, great we have our answer. \n\nIf not, we look for the for palindrome to the left and on the right.\nIf we find anything less or more than these values we are sure to increase the total sum compared to these two values.\nI know, I said it directly but you would get to know if you try to visualize it by doodling it on a paper.\n\nYou are guaranteed to find a palindromic number within 100000 steps on either sides. Why? \nThe closest palindrome you can find is either decreasing or increasing number by 1 for the corners like 9999 or 10000. \nFor all the other cases you can see that by changing the middle most digit of the palindromic number by 1. Gives you the nearest smaller or greater palindromic number. 12321 -> 12121 or 12421. \nSo for 10^9. You are guaranteed to find a palindromic number from median within 10^5 steps (Digits: 10, middle digit = 5. to reach there you need atmost 10^5 steps). \n\nI know my, solution is not perfect. You can find the closest palindrome by taking half of the median and increasing and decreasing the last digit and creating the whole palindromic number. But, this solution provides a stepping stone towards that solution.\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(NlogN): Sorting takes away the magic.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(1): Just variables.\n\n**Feel free to ask any doubts! Would love to help you out. \nIt might even improve my understanding. \nIf there are any mistakes, please point it out! \nHave fun learning!**\n\nIf anyone of you have a more concrete mathematical proof! Please share.\n\n\n# Code\n```\nclass Solution {\npublic:\n\n    bool checkPal(int num) {\n        int b = 0;\n        int a = num;\n        while(a > 0) {\n            b = b*10 + a%10;\n            a = a/10;\n        }\n        return num == b;\n    }\n\n\n    long long cost(vector<int> &nums, int num) {\n        long long c = 0;\n        for(auto &x : nums) {\n            c += abs(x - num);\n        }\n\n        return c;\n    }\n\n    long long minimumCost(vector<int>& nums) {\n        ios_base::sync_with_stdio(false);cin.tie(NULL);\n        int n = nums.size();\n        sort(nums.begin(), nums.end());\n        int median = 0;\n        if(n%2 == 0) {\n            median = (nums[n/2 - 1] + nums[n/2])/2;\n        }   \n        else {\n            median = nums[n/2];\n        }\n        if(checkPal(median)) {\n            return cost(nums, median);\n        }\n\n        int left = median-1;\n        int right = median+1;\n        while(left >= 0 && right <= 1000000001) {\n            if(checkPal(left) && checkPal(right)) {\n                return min(cost(nums, left), cost(nums, right));\n            }\n            else if(checkPal(left)){\n                ++right;\n            }\n            else if(checkPal(right)){\n                --left;\n            }\n            else {\n                --left;\n                ++right;\n            }\n        }\n\n        return -1;\n    }\n};\n```
['C++']