Skip to content

2967. Minimum Cost to Make Array Equalindromic

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
 public:
  long long minimumCost(vector<int>& 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:
  // Returns the cost to change all the numbers to `palindrome`.
  long cost(const vector<int>& nums, int palindrome) {
    return accumulate(nums.begin(), nums.end(), 0L,
                      [palindrome](long acc, int num) {
      return acc + abs(palindrome - num);
    });
  }

  // Returns the palindrome `p`, where p = num + a * delta and a > 0.
  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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
  public long minimumCost(int[] nums) {
    Arrays.sort(nums);
    final int median = nums[nums.length / 2];
    final int nextPalindrome = getPalindrome(median, 1);
    final int prevPalindrome = getPalindrome(median, -1);
    return Math.min(cost(nums, nextPalindrome), cost(nums, prevPalindrome));
  }

  // Returns the cost to change all the numbers to `palindrome`.
  private long cost(int[] nums, int palindrome) {
    return Arrays.stream(nums).mapToLong(num -> Math.abs(palindrome - num)).sum();
  }

  // Returns the palindrome `p`, where p = num + a * delta and a > 0.
  private int getPalindrome(int num, int delta) {
    while (!isPalindrome(num))
      num += delta;
    return num;
  }

  private boolean isPalindrome(int num) {
    final String original = Integer.toString(num);
    final String reversed = new StringBuilder(original).reverse().toString();
    return original.equals(reversed);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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]