Minimum Cost to Make Array Equalindromic solution in C++


class Solution {
 public:
  long long minimumCost(vector& nums) {
    ranges::sort(nums);
    const int median = nums[nums.size() / 2];
    const int nextPalindrome = getPalindrome(median, /*delta=*/1);
    const int prevPalindrome = getPalindrome(median, /*delta=*/-1);
    return min(cost(nums, nextPalindrome), cost(nums, prevPalindrome));
  }

 private:
  long cost(const vector& nums, int palindrome) {
    return accumulate(nums.begin(), nums.end(), 0L,
                      [palindrome](long subtotal, int num) {
      return subtotal + abs(palindrome - num);
    });
  }

  int getPalindrome(int num, int delta) {
    while (!isPalindrome(num))
      num += delta;
    return num;
  }

  bool isPalindrome(int num) {
    const string original = to_string(num);
    const string reversed = {original.rbegin(), original.rend()};
    return original == reversed;
  }
};

Problem Description

Ah, the joys of arrays! You know, those delightful collections of numbers that can sometimes feel like a chaotic family reunion—everyone’s there, but nobody’s getting along. The problem at hand is to transform an array into a palindromic form at the minimum cost. Yes, you heard that right! We want to make sure that the array reads the same forwards and backwards, just like your favorite childhood book that you pretended to read but actually just flipped through the pictures.

Imagine you have a group of friends who insist on wearing matching outfits for a photo. If one of them shows up in a neon green tutu while the others are in classic black, you might need to spend some cash to get everyone on the same page. Similarly, in this problem, we want to adjust the numbers in our array so that they mirror each other, and we want to do it without breaking the bank!

Approach

The approach taken in this solution is quite clever! First, we sort the array to find the median, which serves as a good starting point for our palindrome. Then, we look for the nearest palindromic numbers above and below the median. The cost to convert the entire array to either of these palindromic numbers is calculated, and we simply return the minimum cost.

Time and Space Complexity

Time Complexity: O(n log n) due to the sorting step, where n is the number of elements in the array.
Space Complexity: O(1) since we are using a constant amount of extra space.

Real-World Example

Imagine you’re at a family gathering, and everyone is wearing a different color shirt. You decide to take a family photo, but you want everyone to wear matching shirts. You could either buy a bunch of new shirts or dye the existing ones. The goal is to minimize the cost of making everyone look like they belong to the same family (or at least the same color palette). This is essentially what the problem is asking us to do with the array!

Minimum Cost to Make Array Equalindromic solution in C++

Problem Description

Approach

Time and Space Complexity

Real-World Example

Similar Problems