[C++] Find Palindromic Numbers Near to Median
Intuition\n Describe your first thoughts on how to solve this problem. \n- Change all the numbers in the array into a palindromic number, which is neat to the m
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Change all the numbers in the array into a palindromic number, which is neat to the median of the array\n- If the median is palindromic, it is the best choice\n  - Otherwise, there are 2 palindromic numbers near the median\n  - Try all of them and choose the better one\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Sort the array\n- Find the median\n- Find the best palindromic number\n\n# Complexity\n- Time complexity: $$O({n}\\times{\\log{n}})$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    long long minimumCost(vector<int>& nums) {\n        // sort the array\n        sort(nums.begin(), nums.end());\n\n        // find the median\n        int n = nums.size();\n        long long median = (nums[n / 2] + nums[(n - 1) / 2]) / 2;\n        \n        // if the median is palindromic, it is the best choice\n        if (isPalindromic(median)) return getCost(nums, median);\n\n        // try the palindromic numbers that are near to the median\n        return min(\n            getCost(nums, getNextNumber(median)),\n            getCost(nums, getPrevNumber(median))\n        );\n    }\nprivate:\n    bool isPalindromic(long long x) {\n        long long y = 0LL, z = x;\n        while (x > 0) {\n            y = 10LL * y + (x % 10LL);\n            x /= 10LL;\n        }\n        return (y == z);\n    }\n    long long getNextNumber(long long x) {\n        while (!isPalindromic(x)) x++;\n        return x;\n    }\n    long long getPrevNumber(long long x) {\n        while (!isPalindromic(x)) x--;\n        return x;\n    }\n    long long getCost(vector<int>& nums, long long x) {\n        long long cost = 0LL;\n        for (auto& num : nums) cost += abs((long long)num - x);\n        return cost;\n    }\n};\n```
['Brainteaser', 'Sorting', 'C++']