O(N) fastest solution, 2 pass, using quick median, no brute force
Intuition\n Describe your first thoughts on how to solve this problem. \n- find the medians of the nums.\n- if x is not required to be a palindrome, the min of 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- find the medians of the nums.\n- if x is not required to be a palindrome, the min of sum|nums[i]-x| will be when x==median.\n- since x must be a palindrome, then check the adjacent palindromic numbers of the medians. \n# Approach\n<!-- Describe your approach to solving the problem. -->\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```\n/*\nAlgo:\n- find the medians of the nums.\n- if x is not required to be a palindrome, the min of sum|nums[i]-x| will be when x==median.\n- \n*/\nstatic constexpr  int flip(int k){\n    int ans = 0;\n    while (k) {\n        ans = ans*10 + (k%10);\n        k /= 10;\n    }\n    return ans;\n}\n\n\nclass Solution {\n    \n    static int numdigits(int i) {\n        return i > 0 ? (int) log10 ((double) i) + 1 : 1;\n    }\n\n    static auto cost(const vector<int>&nums, int64_t k1, int64_t k2){\n        int64_t ans1 = 0, ans2 = 0;\n        for (int n:nums) {\n            ans1 += std::abs(n-k1);\n            ans2 += std::abs(n-k2);\n        }\n        return std::min(ans1,ans2);\n    }\n    \n   // biggest palin <= k\n    static int biggestpalin(int k){\n        const int d = numdigits(k);\n        if (k==1) return k;\n        if (pow(10, d-1) == k) return k-1;\n        const int mul = pow(10, d/2);\n        const int oddmul = pow(10, d%2);\n        int upperhalf = k/mul; // include center median digit\n        int lowerhalf = flip(upperhalf/oddmul);\n        int ans = upperhalf * mul + lowerhalf;\n        if (ans <= k) return ans;\n        upperhalf--;\n        return upperhalf * mul + flip(upperhalf/oddmul);\n    }\n\n    // smallest palin >= k\n    static int smallestpalin(int k){\n        const int d = numdigits(k);\n        const int mul = pow(10, d/2);\n        const int oddmul = pow(10, d%2);\n        int upperhalf = k/mul; // include center median digit\n        int lowerhalf = flip(upperhalf/oddmul);\n        int ans = upperhalf * mul + lowerhalf;\n        if (ans >= k) return ans;\n        upperhalf++;\n        return upperhalf * mul + flip(upperhalf/oddmul);\n    }\n\n    // s and e are inclusive\n    // kth is 0-based\n    static int quickmedian( std::vector<int>& nums, int s, int e, int kth){\n        if (s >= e) return nums[s];\n\n        int storeidx = s;\n        const int m = s + (e-s)/2;\n        const int pivot = nums[m];\n        std::swap(nums[m], nums[e]);\n        for (int i=s; i < e; i++){\n            if (nums[i] < pivot) {\n                std::swap(nums[i], nums[storeidx]);\n                storeidx++;\n            }\n        }\n        std::swap(nums[storeidx], nums[e]);\n        if (storeidx < kth) {\n            return quickmedian(nums, storeidx+1, e, kth);\n        }\n        return quickmedian(nums, s, storeidx, kth);\n    }\n\npublic:\n    long long minimumCost(vector<int>& nums) {\n        \n        int m = quickmedian(nums, 0, nums.size()-1, (nums.size())/2);\n        return cost(nums, biggestpalin(m),  smallestpalin(m));\n    }\n};\n```
['C++']