O(N) time and space solution c++, beats 93% solutions in time
Intuition\n Describe your first thoughts on how to solve this problem. \nThe cost of making all element same is minimum when we make all elements equal to the m
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe cost of making all element same is minimum when we make all elements equal to the mediam element of the array. \nExample:\n1) 1 4 10 : minimum cost is when we make all elements equal to 4 \nabs(1-4) + abs(4-4) + abs(10-1) = 12\n \n2) 1 3 10 12 :  minimum cost is when we make all elements equal to either 3 or 4 or 5 or .. 10. Suprising fact is cost will be same for all elements from 3 to 10. So here we have multiple choices. \n\nThe cost increases linearly as and when we take smaller or bigger element than median.\n\n# Approach\nNow we can use "nth_element" function to get median in O(n).  \nThen create two functions which can get us just smaller or just greater palindrome. \nThen we find two possible palindromes nearest to median elements. (two meadian\'s in case of even no. of elements)\n\nThen just return whichever givnes minimum results.\n\n# Complexity\n- Time complexity: O(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```\nclass Solution {\n    long long ans(vector<int>& nums, long long k) {\n        long long ans = 0;\n        for(int x:nums)\n            ans+=abs(x-k);\n        return ans;\n    }\n        \n    int just_smaller_or_equal(int x) {\n        string s = to_string(x);\n        int n=s.size(),i;\n        for(i=(n+1)/2; i<n && s[i]==s[n-1-i];i++) ;\n\n        if(i==n) {\n            return stoi(s);\n        }\n        if(s[i]>s[n-i-1]) {\n            for(;i<n;i++) {\n                s[i]=s[n-i-1];\n            }\n        } else {\n            for(i=(n-1)/2;i>=0 && s[i]==\'0\';i--) ;\n            s[i]--;\n            if(i==0 && s[i]==\'0\') {\n                for(i=0;i<n-1;i++)\n                    s[i]=\'9\';\n                s.pop_back();\n            } else{\n                for(i++;i<=(n-1)/2;i++)\n                    s[i]=\'9\';\n                for(i=(n+1)/2;i<n;i++)\n                    s[i]=s[n-1-i];\n            }\n        }\n        return stoi(s);\n    }\n    \n    int just_greater_or_equal(int x) {\n        string s = to_string(x);\n        int n=s.size(),i;\n        for(i=(n+1)/2 ; i<n && s[i]==s[n-1-i];i++) ;\n        if(i==n) {\n            return stoi(s);\n        }\n        if(s[i]<s[n-i-1]) {\n            for(;i<n;i++) {\n                s[i]=s[n-i-1];\n            }\n        } else {\n            for(i=(n-1)/2;i>=0 && s[i]==\'9\';i--) ;\n            s[i]++;\n            for(i++;i<=(n-1)/2;i++)\n                s[i]=\'0\';\n            for(i=(n+1)/2;i<n;i++)\n                s[i]=s[n-1-i];\n        }\n        return stoi(s);\n    }\n    \npublic:\n    long long minimumCost(vector<int>& nums) {\n        int x,y;\n        if(nums.size()%2) {\n            nth_element(nums.begin(), nums.begin() + nums.size()/2, nums.end());\n            int mid = nums[nums.size()/2];\n            x = just_smaller_or_equal(mid);\n            y = just_greater_or_equal(mid);\n        } else {\n            nth_element(nums.begin(), nums.begin() + nums.size()/2 - 1, nums.end());\n            int L = nums[nums.size()/2-1];\n            nth_element(nums.begin(), nums.begin() + nums.size()/2, nums.end());\n            int R = nums[nums.size()/2];\n\n            x = just_smaller_or_equal(R);\n            y = just_greater_or_equal(L);\n        }\n        \n        long long ans_x = ans(nums,x);\n        long long ans_y = ans(nums,y);\n    \n        return min(ans_x,ans_y);\n    }\n};\n```
['C++']