Minimum Cost to Make Array Equalindromic solution in Python

Problem Description

So, you think you can just throw a bunch of numbers into an array and call it a day? Well, think again! The problem at hand is to transform an array into a palindromic array at the minimum cost. Yes, you heard it right! We want to make sure that the array reads the same backward as forward, just like your favorite childhood book.

Imagine you have a group of friends who insist on wearing matching outfits for a party. But alas, they all show up in different colors! Your job is to make them all wear the same color at the least expense. In this case, the “color” is the palindromic number you need to convert your array into.

Code Solution


class Solution:
    def minimumCost(self, nums: list[int]) -> int:
        nums.sort()
        median = nums[len(nums) // 2]
        nextPalindrome = self._getPalindrome(median, delta=1)
        prevPalindrome = self._getPalindrome(median, delta=-1)
        return min(self._cost(nums, nextPalindrome),
                   self._cost(nums, prevPalindrome))

    def _cost(self, nums: list[int], palindrome: int) -> int:
        """Returns the cost to change all the numbers to `palindrome`."""
        return sum(abs(palindrome - num) for num in nums)

    def _getPalindrome(self, num: int, delta: int) -> int:
        """Returns the palindrome `p`, where p = num + a * delta and a > 0."""
        while not self._isPalindrome(num):
            num += delta
        return num

    def _isPalindrome(self, num: int) -> int:
        original = str(num)
        return original == original[::-1]

Approach Explanation

The code starts by sorting the array and finding the median. Why the median, you ask? Because it’s the middle ground, the Switzerland of numbers! Then, it calculates the nearest palindromic numbers above and below the median. Finally, it computes the cost to convert all numbers in the array to these palindromic numbers and returns the minimum cost.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n log n)
Space Complexity	O(1)

Real-World Example

Let’s say you’re organizing a family reunion, and everyone has a different favorite dish. You want to make sure that everyone ends up eating the same dish (the palindromic number) to avoid chaos. The cost here could be the effort and resources spent on cooking or ordering that dish. The goal is to minimize that cost while ensuring everyone is happy and fed!