Make all array elements equal with minimum cost Medium 0 attempts
GeeksforGeeks ↗

Make all array elements equal with minimum cost

Medium Sorting&Searching GeeksforGeeks

Given an array of integers, find the minimum total cost to make all elements equal. The cost of changing an element from value a to value b is |a - b|. The optimal target value that minimizes the total absolute deviation is the median of the array.

Example 1:

Input: arr = [1, 100, 101]
Output: 100

Example 2:

Input: arr = [1, 2, 3]
Output: 2
Sample Input
—
Sample Output
—
Constraints
  • 1 <= N <= 10^5
  • 1 <= A[i] <= 10^5
Test Cases
Case 1
Args: [[1,100,101]] Expected: 100
Topics
Sorting&Searching

Approach: Sort + Median

Sort the array and pick the median element as the target. The median minimizes the sum of absolute deviations. Compute the total cost as the sum of absolute differences from the median.

function makeAllArrayElementsEqualWithMinimumCost(arr) {
  arr.sort((a, b) => a - b);
  const median = arr[Math.floor(arr.length / 2)];
  return arr.reduce((sum, x) => sum + Math.abs(x - median), 0);
}

Time Complexity: O(n log n)

Space Complexity: O(1)

Saved in this browser only. Private to you.

JavaScript