Make array elements equal with minimum cost

Given an array which contains integer values, we need to make all values of this array equal to some integer value with minimum cost where the cost of changing an array value x to y is abs(x-y).

Example 1

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

Output: 100

We can change all its values to 100 with minimum cost,

|1 - 100| + |100 - 100| + |101 - 100| = 100

Example 2

Input : arr[] = [4, 6]

Output: 2

We can change all its values to 5 with minimum cost,

|4 - 5| + |5 - 6| = 2

Approach

1. Sort the given array in non-decreasing order.
2. Calculate the median of the sorted array. The median is the middle value if the array length is odd, or the average of the two middle values if the array length is even.
3. Initialize a variable to keep track of the minimum cost.
4. For each element in the array, calculate the absolute difference between the element and the calculated median.
5. Sum up all the absolute differences to find the minimum cost.
6. Return the minimum cost as the result.

This approach leverages the fact that the median minimizes the total absolute difference between the array elements and itself, making it the optimal choice to minimize the cost of making all values equal.

Complexity

• Time Complexity: O(n*log n), where 'n' is the length of the input array.
• Space Complexity: O(1), because the code uses a fixed number of variables.

Code

# Java Code

import java.util.Arrays;

public class MinimizeCost {

    public static int minimizeCost(int[] arr) {

        int n = arr.length;
        if (n == 0) {
            return 0;
        }

        // Sort the array
        Arrays.sort(arr);

        // Calculate the median
        int median = arr[n / 2];

        // Calculate the minimum cost
        int cost = 0;
        for (int x : arr) {
            cost += Math.abs(x - median);
        }

        return cost;
    }

    public static void main(String[] args) {
        int[] arr = {1, 100, 101};
        int minCost = minimizeCost(arr);
        System.out.println("Minimum cost to make all values equal: " + minCost);
    }
}

Output

Minimum cost to make all values equal: 100