C++ || RunTime: O(nlogn) || Median✅ Mean❌, Explained Solution
Approach\nThe approach was simple, first find the median, find a palindromic number near to the median, which gives minimum cost.\n\nVariables\n1. median: the m
# Approach\nThe approach was simple, first find the median, find a palindromic number near to the median, which gives minimum cost.\n\nVariables\n1. `median`: the median for the vector `nums`\n2. `lowerPalin`: the largest palindromic number which is just less than or equal to `median`.\n3. `upperPalin`: the smallest palindromic number which is greater or equal to `median`.\n\n### Why not Mean?\nI was also inclined toward using `mean` instead of `median`, but soon I realised that it would fail in cases like `[1,2,3,4,5,111]` where numbers like `111` pushed the mean to greater side, where as `median` was in central and helped calculating the nearest palindrome better.\n\n**Explanation**\nExample array: `[1,2,3,4,5,111]`\nSo for this array, mean will be `21`, and median will be `3.5`\n-- With `mean = 21`, `lowerPalin` will be `11` and `upperPalin` will be `22`, and cost with `lowerPalin` will be `140` and that with `upperPalin` with be `184`. So the cost with mean will be `min(140, 184)` ie`meanCost = 140`.\n-- With `median = 3.5`, `lowerPalin` will be `3` and `upperPalin` will be `4`, and cost with `lowerPalin` will be `114` and that with `upperPalin` with be `114`. So the cost with median will be `min(114, 114)` ie`medianCost = 114`.\n\nThus we can clearly see that **with median we are able to generate lower cost than mean**. \n\n# Algorithm\nMade a few helper functions like: \n1. `bool isPalindrome(int x)` : returns `true` if the number `x` is a Palindromic number, else returns `false`\n2. `double findMedian(vector<int> a, int n)`: returns the median of the `vector a`, where `n` is the size of the vector\n3. `long long calcCost(vector<int>& arr, int palin)`: returns the cost of the `vector arr`, when it\'s integers are converted to the palindrome number `palin`.\n\nAlgorithm for `minimumCost()`\n1. Find the `median` of `nums`. \n2. Check if `median` is a decimal number or not. This is done if `median` is a decimal number then `upperPalin` will be `median + 1`. \n    Additionally I also checked if `median` itself is a palindromic number, if it is we return the minimum cost right here. (Greedy Approach)\n3. Loop and decrease `lowerPalin` variable till we find the largest palindromic number which is just less than or equal to `median`\n4. Loop and increase `upperPalin` variable till we find the smallest palindromic number which is greater or equal to `median`.\n5. Check if we found `lowerPalin`, ie `lowerPalin == 0` if this is true, then we didnt find a lowerPalin because of the constraints that the number should be in range [1, 10^9]. Similarly check `upperPalin`\n6. Return the minimum cost with `lowerPalin` and `upperPalin`.\n\n# Complexity\n- Time complexity:\n$$O(n*logn)$$\n\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution {\npublic:\n    bool isPalindrome(int x, int &y) {\n        if (x < 0) return false;\n        if (x == 0) return true;\n        if (isPalindrome(x/10, y) && (x%10 == y%10)) {\n            y /= 10;\n            return true;\n        } else {\n            return false;\n        }\n    }\n    \n    bool isPalindrome(int x) {\n        return isPalindrome(x, x);\n    }\n    \n    long long calcCost(vector<int>& arr, int palin) {\n        long long ans = 0; \n        for(int a : arr) {\n            ans += abs(a - palin);\n        }\n        return ans;\n    }\n    \n    double findMedian(vector<int> a, int n) { \n        if (n % 2 == 0) { \n            nth_element(a.begin(), \n                        a.begin() + n / 2, \n                        a.end()); \n\n            nth_element(a.begin(), \n                        a.begin() + (n - 1) / 2, \n                        a.end()); \n\n            return (double)(a[(n - 1) / 2] \n                            + a[n / 2]) \n                   / 2.0; \n        } \n        else { \n            nth_element(a.begin(), \n                        a.begin() + n / 2, \n                        a.end()); \n            return (double)a[n / 2]; \n        } \n    } \n    \n    long long minimumCost(vector<int>& nums) {\n        int len = nums.size();\n        double median = findMedian(nums, len);\n        long long lowerPalin = median;\n        long long upperPalin;\n        if(median - int(median) == 0.0) {\n            if(isPalindrome(lowerPalin))\n                return calcCost(nums, lowerPalin);\n            else \n                upperPalin = lowerPalin;\n        }\n        else \n            upperPalin = lowerPalin + 1;\n            \n        while(lowerPalin > 0 and !isPalindrome(lowerPalin)) \n            lowerPalin--;\n        while(upperPalin < 1000000000 and !isPalindrome(upperPalin))\n            upperPalin++;\n        \n        if(lowerPalin == 0)\n            return calcCost(nums, upperPalin);\n        if(upperPalin == 1000000000) \n            return calcCost(nums, lowerPalin);\n\n        return min(calcCost(nums, lowerPalin), calcCost(nums, upperPalin));\n    }\n};\n```\n\n---\n\n*PS: tried leetcode after a almost 1.5yrs, didnt think I would be able to solve the third ques of this contest, but here we did. The grind is back on. If you read this far, keep grinding and I wish good fortunes for you in next contests :D*
['Greedy', 'C++']