Make Array Elements Equal
You are given an array of integers of size ‘N’. You have to make the elements of the array equal, and the cost of changing the element ‘x’ to ‘y’ is abs(x -y). Your task is to find the minimum cost to make the elements of the array equal.

For example:

Consider ARR = [3, 4, 5] now suppose if we want to change every element value to 4, then the cost of changing 3 to 4 is |3 - 4| which is 1, and the cost of changing 5 to 4 is |5 - 4| which is 1, so the total cost is 1 + 1 = 2. The value 2 is the minimum cost to make all values in the array equal. Hence, the answer is 2.

Input Format:

The first line of the input contains an integer ‘T’ denoting the number of test cases. The first line of each test case contains a single integer, ‘N’, denoting the number of elements in the array. The second line of each test case contains 'N' space-separated integers denoting the elements of the array.

Output Format:

For each test case, print the minimum cost to make elements of the array equal. Print the output of each test case in a separate line.

Constraints:

1

Question

Make Array Elements Equal

You are given an array of integers of size ‘N’. You have to make the elements of the array equal, and the cost of changing the element ‘x’ to ‘y’ is abs(x -y). Your task is to find the minimum cost to make the elements of the array equal.

For example:

Consider ARR = [3, 4, 5] now suppose if we want to change every element value to 4, then the cost of changing 3 to 4 is |3 - 4| which is 1, and the cost of changing 5 to 4 is |5 - 4| which is 1, so the total cost is 1 + 1 = 2. The value 2 is the minimum cost to make all values in the array equal. Hence, the answer is 2.

Input Format:

The first line of the input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains a single integer, ‘N’, denoting the number of elements in the array.
The second line of each test case contains 'N' space-separated integers denoting the elements of the array.

Output Format:

For each test case, print the minimum cost to make elements of the array equal.     

Print the output of each test case in a separate line.

Constraints:

1 <= T <= 5
1 <= N <= 10^5
1 <= ARR[i] <= 10^8

Time limit: 1 sec

Accepted Answer

Approach :

1) We will initialize the variable lowerLimit and upperLimit with the minimum and maximum value present in the array.

2) Iterate while upperLimit - lowerLimit is more than 2.
2.1) Set the variables mid1 with lowerLimit + (upperLimit - lowerLimit)/3 and mid2 with upperLimit - (upperLimit - lowerLimit)/3.

2.2) Initialize the variable cost1 with the cost of converting all array elements to mid1. You have to iterate the complete array to calculate cost1.

2.3) Similarly, find cost2 by keeping mid2 as the target value of all elements in the array.

2.4) If cost1 is less than cost2 then set upperLimit as mid2; otherwise, set lowerLimit as mid1.

3) Set target as (lowerLimit + upperLimit)/2 and cost as 0. The variable cost stores the minimum cost to convert all elements present in the array to target.

4) Iterate index from 0 to N-1.
4.1) Increment cost by an absolute difference of ARR[index] and target.

5) Return the variable cost.

TC : O(N * log(Max(ARR) - Min(ARR))) where N = size of the array.
SC : O(1)

Accepted Answer

Brute Force

In this approach, we will traverse the array for each value between the minimum and maximum value of the array. We will find the cost for each value to make the elements of the array equal to that particular value. We will maintain a variable minimumCost that stores the minimum cost from all these costs.

For example, ARR = [2, 16, 11], then we will find the cost needed to convert every element in the array to the particular value for each value between 2 and 16. We have to maintain minimumCost to store the minimum cost. In the end, the variable minimumCost is our answer.

Algorithm:

We will initialize the variable minimumCost with the maximum integer value, and it will store the minimum cost needed to make array elements equal.
We will initialize the variable currentCost with 0, and it will store the cost needed to make array elements equal to the current element.
We will initialize the variable lowerLimit and upperLimit with the minimum and maximum value present in the array ARR.
Iterate val from lowerLimit to upperLimit.
- Iterate the array ARR and increment the currentCost with the cost needed to convert the element to val.
- If currentCost is less than minimumCost, then update the variable minimumCost with currentCost.
- Update the variable currentCost to 0.
Return the minimumCost variable.

Space Complexity: O(1)Explanation:

O(1).

Constant space is being used. Hence, the overall Space Complexity is O(1).

Time Complexity: OtherExplanation:

O(N * (Max(ARR) - Min(ARR))) where N is the number of elements in the array.

For each value less than or equal to Min(ARR) and greater than or equal to Max(ARR), we are traversing the array completely to find the cost, so the overall complexity is O(N * (Max(ARR) - Min(ARR))).

Python (3.5)

"""

    Time Complexity: O(N * (Max(ARR) - MIN(ARR)))

    Space Complexity: O(1)



    Where N is the number of elements in array

"""



from sys import maxsize



def findMinimumCost(arr, n):

    

    # Variable which stores the minimum cost

    minimumCost = maxsize



    currentCost = 0



    # Variable which stores the minimum and maximum value in the array

    lowerLimit = min(arr)

    upperLimit = max(arr)



    for val in range(lowerLimit, upperLimit + 1):



        # Loop to find cost by using val as target value

        for j in range(0, n):

            currentCost = currentCost + abs(arr[j] - val)



        # Updating minimumCost variable

        minimumCost = min(minimumCost, currentCost)

        

        currentCost = 0



    # Return minimumCost 

    return minimumCost

C++ (g++ 5.4)



/*

    Time Complexity: O(N * (Max(ARR) - MIN(ARR)))

    Space Complexity: O(1)



    Where N is the number of elements in array

*/



# include 

#include 

#include 



int findMinimumCost(vector &arr, int n)

{    

    // Variable which stores the minimum cost

    int minimumCost = INT_MAX;



    int currentCost = 0;



    // Variable which stores the minimum and maximum value in the array

    int lowerLimit = *min_element(arr.begin(), arr.end());

    int upperLimit = *max_element(arr.begin(), arr.end());



    for (int val = lowerLimit ; val < upperLimit + 1; val++)

    {

        // Loop to find cost by using val as target value

        for(int j= 0; j < n ; j++)

        {

            currentCost = currentCost + abs(arr[j] - val);

        } 

            

        // Updating minimumCost variable

        minimumCost = min(minimumCost, currentCost);

        

        currentCost = 0;

    }



    // Return minimumCost 

    return minimumCost;

}

Java (SE 1.8)


/*
    Time Complexity: O(N * (Max(ARR) - MIN(ARR)))
    Space Complexity: O(1)

    Where N is the number of elements in array
*/

import java.util.Arrays;

public class Solution {
	public static int findMinimumCost(int[] arr, int n) {
		// Variable which stores the minimum cost
		int minimumCost = Integer.MAX_VALUE;

		int currentCost = 0;
		int copyArray[] = arr;
		Arrays.sort(arr);

		// Variable to contain minimum value of array
		int lowerLimit = copyArray[0];

		// Variable to contain maximum value )of array
		int upperLimit = copyArray[n - 1];

		for (int val = lowerLimit; val < upperLimit + 1; val++) {
			// Loop to find cost by using val as target value
			for (int j = 0; j < n; j++) {
				currentCost = currentCost + Math.abs(arr[j] - val);
			}

			// Updating minimumCost variable
			minimumCost = Math.min(minimumCost, currentCost);

			currentCost = 0;
		}

		// Return minimumCost
		return minimumCost;
	}

}

Accepted Answer

Binary Search

In this one pattern, as we increase the target value, the cost decreases up to a limit then starts increasing, which means some U shape graph is present. We have to find the lowest cost, which is the lowest point of this U shape graph, so for this, we are going to use the ternary search here and set the highest and lowest value of the array as limits, and then we will keep skipping 1/3 part of the search space until we reach to the bottom-most point of our U-curve.