O(N) Time, O(1) space solution (6ms beats 100% Java)
Code


# Code
```java []
class Solution {
    public long minimumCost(int[] nums) {
        //just find closest palindrome to the median
        int[] med = getMedian(nums);
        long leftPal = palLess(med[0]), rightPal = palGreater(med[med.length-1]);
        long costLeft = 0, costRight = 0;
        for(int num : nums) {
            costLeft += Math.abs(num - leftPal);
            costRight += Math.abs(num - rightPal);
        }

        return Math.min(costLeft, costRight);
    }

    private static long palGreater(long limit) { //returns the smallest palindrome >= limit
        /*observe: this palindrome must have the same digit count as limit, as if it had a greater digit count, 
        the palindrome of all 9's with same number of digitts would be smaller than it yet still >= limit, as all 9's is the highest possible
        number for some arbitrary digit count.
        This means for odd digit cnt limit, pal is of odd lenn and even digit cnt lim, pal is of even len.
           
        Observation for even length palidrome, a palindrome is uniquely determined by the first len/2 digits and odd len are uniquely dettermined by first (len+1)/2 digits
        this is because other digits just end up a reflection of these.
        Thus, if limit is of even len, can start with a palindrome that has the same first half as limit, try this one, if it isn't >=  then move to nnext one usinng firstHalf + 1
        */
        long digitCount = 0, pow10;
        for(pow10 = 1; pow10 <= limit; pow10 *= 10) digitCount++;
        long start = 0, end = 0, num = limit, endPlace = 1;
        for(int i = 0; i < digitCount/2; i++) {
            pow10 /= 10;
            start = start*10 + num/pow10;
            end += endPlace * (num/pow10);
            endPlace *= 10;
            num %= pow10;
        }
        long mid = (10*num)/pow10;
        long lowPal = (digitCount % 2 == 0 ? start : start*10 + mid)*endPlace + end;
        if(lowPal >= limit) return lowPal;
        if(digitCount % 2 == 1) return mid < 9 ? lowPal + endPlace : (start+1)*10*endPlace + reverse(start+1);

        return (start+1)*endPlace + reverse(start+1);
    }

    private static long palLess(long limit) {
        long digitCount = 0, pow10;
        for(pow10 = 1; pow10 <= limit; pow10 *= 10) digitCount++;
        long start = 0, end = 0, num = limit, endPlace = 1, pow = pow10;
        for(int i = 0; i < digitCount/2; i++) {
            pow /= 10;
            start = start*10 + num/pow;
            end += endPlace * (num/pow);
            endPlace *= 10;
            num %= pow;
        }
        long mid = (10*num)/pow;
        long hiPal = (digitCount % 2 == 0 ? start : start*10 + mid)*endPlace + end;
        if(hiPal <= limit) return hiPal;
        long res;
        if(digitCount % 2 == 1) {
            res = mid > 0 ? hiPal - endPlace : (start-1)*10*endPlace + reverse(start-1);
        } else {
            res = (start-1)*endPlace + reverse(start-1);
        }
        return res < pow10/10 ? pow10/10 - 1 : res;
    }

    private static long reverse(long num) {
        long rev = 0;
        while(num > 0) {
            rev = rev*10 + (num % 10);
            num /= 10;
        }
        return rev;
    }
    private static int[] getMedian(int[] nums) {
        int n = nums.length, candidate = 0, count = 0;
        for(int num : nums) {
            if(count == 0) {
                candidate = num;
                count = 1;
            } else if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        count = 0;
        for(int num : nums) if(num == candidate) count++;
        if(count > n/2) return new int[]{candidate};
        if(n % 2 == 1) return new int[]{quickSelect(0, n-1, n/2, nums, new Random())};

        int medLeft = quickSelect(0, n-1, n/2 - 1, nums, new Random());
        int leftInd = 0;
        for(int num : nums) if(num >= medLeft) leftInd++;
        if(leftInd >= n/2) return new int[]{medLeft};

        int medRight = Integer.MAX_VALUE;
        for(int num : nums) if(num > medLeft && num < medRight) medRight = num;
        return new int[]{medLeft, medRight};
    }

    private static int quickSelect(int left, int right, int k, int[] nums, Random rand) {
        int partIndex = partition(left, right, rand.nextInt(right-left+1) + left, nums);

        if(partIndex == k) {
            return nums[partIndex];
        } else if (partIndex > k) {
            return quickSelect(left, partIndex-1, k, nums, rand);
        } else {
            return quickSelect(partIndex+1, right, k, nums, rand);
        }
    }

    private static int partition(int left, int right, int pivIndex, int[] nums) {
        int pivot = nums[pivIndex];
        nums[pivIndex] = nums[right];

        int pivPos = left;
        for(int i = left; i < right; i++) {
            if(nums[i] < pivot) {
                int temp = nums[i];
                nums[i] = nums[pivPos];
                nums[pivPos++] = temp;
            }
        }


        nums[right] = nums[pivPos];
        nums[pivPos] = pivot;
        return pivPos;
    }
}
```
['Java']