Minimum Cost to Make Array Equalindromic — Medium Problem & Solution

Problem statement

You are given an integer array nums. You may change every element to one common value y, paying |nums[i] - y| for each element i.

The array is equalindromic when all its elements equal the same palindromic positive integer — a number that reads the same forwards and backwards in base 10, such as 7, 44 or 121.

Return the minimum total cost to make nums equalindromic.

The original allows up to 10^5 values of up to 10^9; here n <= 10^4 and values are at most 10^5, so the cost always fits in a 32-bit integer.

Example 1

Input: nums = [10,12,13,14,15]
Output: 11
Explanation: Change everything to the palindrome 11: 1 + 1 + 2 + 3 + 4 = 11.

Example 2

Input: nums = [101,104,99,250]
Output: 154
Explanation: Choosing 101 costs 0 + 3 + 2 + 149.

Example 3

Input: nums = [22,33,22,33,22]
Output: 22

Constraints

• 1 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^5

How to solve Minimum Cost to Make Array Equalindromic

The cost f(y) = sum |nums[i] - y| is convex and minimised at the median. Moving away from the median in either direction never helps, so the best palindrome is one of the two palindromes that bracket the median.

Approach

1. Sort nums and take the median m = nums[n / 2].
2. Step down from m until reaching a palindrome lo, and up from m until reaching a palindrome hi.
3. Return min(f(lo), f(hi)), computing each sum in 64-bit arithmetic.

Why it works

f is flat between the two middle elements and strictly sloped outside them, so it is non-increasing up to the median and non-decreasing after it. Any palindrome below lo costs at least f(lo), and any palindrome above hi costs at least f(hi). Palindromes are dense enough (gaps of at most 110 below 10^5) that the stepping is short.

Complexity

• Time — O(n log n)
• Space — O(n)

Pitfalls

• Checking only the nearest palindrome to the median by distance is wrong — compare the costs of both neighbours.
• With an even length either middle element works as the median, because f is flat between them.
• Accumulate the cost in 64 bits in fixed-width languages even though the tightened answer fits in int32.

Reference solution

Python

from typing import List

def minimumCost(nums: List[int]) -> int:
    a = sorted(nums)
    med = a[len(a) // 2]

    def is_pal(x):
        s = str(x)
        return s == s[::-1]

    lo = med
    while not is_pal(lo):
        lo -= 1
    hi = med
    while not is_pal(hi):
        hi += 1
    return min(sum(abs(v - lo) for v in a), sum(abs(v - hi) for v in a))

JavaScript

var minimumCost = function(nums) {
    var a = nums.slice().sort(function(x, y) { return x - y; });
    var med = a[a.length >> 1];
    var isPal = function(x) {
        var r = 0, t = x;
        while (t > 0) { r = r * 10 + (t % 10); t = Math.floor(t / 10); }
        return r === x;
    };
    var cost = function(y) {
        var s = 0;
        for (var i = 0; i < a.length; i++) s += Math.abs(a[i] - y);
        return s;
    };
    var lo = med, hi = med;
    while (!isPal(lo)) lo--;
    while (!isPal(hi)) hi++;
    return Math.min(cost(lo), cost(hi));
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Non-decreasing Subsequences Medium
• Construct the Lexicographically Largest Valid Sequence Medium
• Matchsticks to Square Medium
• Combination Sum III Medium
• Combination Sum II Medium
• Permutations II Medium