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

Make all array elements equal with minimum cost

Medium Sorting&Searching GeeksforGeeks

You're given an array of integers, and you want every element to end up with the same value for the lowest possible total cost. Changing a single element from a to b costs |a - b|. Picking the array's median as the common target value is what minimizes this total cost.

Input Format
Implement makeAllArrayElementsEqualWithMinimumCost(arr). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

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

Example 2

Input
arr = [5,5]
Output
0
Constraints
  • 1 <= N <= 10^5
  • 1 <= A[i] <= 10^5
Test Cases (2)
Case 1
Args: [[1,100,101]] Expected: 100
Case 2
Args: [[5,5]] Expected: 0
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.

javascript
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