n*log(n) time complexity solution || explained with comments
Complexity\n- Time complexity: O( n*log(n) )\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(n)\n Add your space complexity here, e.g. O(n)
# Complexity\n- Time complexity: O( n*log(n) )\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\ntypedef long long ll;\n\nclass Solution {\npublic:\n    // to check  for palindrome\n    bool isPalindrome(ll x) {\n        if(x == 0 || x < 10)\n            return true;\n        \n        ll n = x, i = 0 ,rev = 0;\n        while(n != 0) {\n            ll r = n % 10;\n            rev = rev*10 + r;\n            n = n / 10;\n        }\n        \n        if(rev == x)\n            return true;\n        return false;\n    }\n\n    // to get left and right nearest palindrome for median\n    pair<ll, ll> findNearestPalindrome(ll median) {\n        ll left = median-1, right = median;\n        while(left > 0 && !isPalindrome(left)) {\n            left--;\n        }\n        while(right <= 1e9 && !isPalindrome(right)) {\n            right++;\n        }\n        return {left, right};\n    }\n    \n    // find cost using binary search and prefix sum in log(n) time complexity\n    ll findCost(vector<int>& nums, vector<ll> &pre, ll palin) {\n        ll n = nums.size();\n        ll cost = 0, sum = pre[n-1];\n\n        // edge cases\n        if(palin < nums[0])\n            return sum - palin*n;\n        if(palin > nums[n-1])\n            return palin*n - sum;\n        \n        // binary search\n        ll left = 0, right = n-1, i = 0;\n        while(left <= right) {\n            ll mid = (left + right) /2;\n            if(nums[mid] <= palin) {\n                i = mid;\n                left = mid + 1;\n            }\n            else\n                right = mid-1;\n        }\n\n        cost = (palin*(i+1) - pre[i]) + ((sum-pre[i]) - (n-i-1)*palin); // O(1)\n\n        return cost;\n    }\n    \n    long long minimumCost(vector<int>& nums) {\n        int n = nums.size();\n        vector<ll> pre(n, 0);\n        sort(nums.begin(), nums.end());\n\n        // calculate prefix sum\n        pre[0] = nums[0];\n        for(int i = 1; i < n; i++) {\n            pre[i] = pre[i-1] + nums[i];\n        }\n        \n        ll median = nums[n/2];\n        pair<ll, ll> pp = findNearestPalindrome(median);\n        \n        ll cost = LLONG_MAX;\n        // check for left nearest neighbour palindrome\n        if(isPalindrome(pp.first))\n            cost = min(cost, findCost(nums, pre, pp.first));\n\n        // check for rightt nearest neighbour palindrome\n        if(isPalindrome(pp.second))\n            cost = min(cost, findCost(nums, pre, pp.second));\n        \n        // check for all array elements\n        for(int i = 0; i < nums.size(); i++) {\n            if(isPalindrome(nums[i]))\n                cost = min(cost, findCost(nums, pre, nums[i]));\n        }\n        \n        return cost;\n    }\n};\n```
['C++']