Last Updated: 4 Jul, 2021
Make Array Elements Equal
Moderate
Asked in companies
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
Approaches
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.
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.
Algorithm:
- We will initialize the variable lowerLimit and upperLimit with the minimum and maximum value present in the array.
- Iterate while upperLimit - lowerLimit is more than 2.
- Set the variables mid1 with lowerLimit + (upperLimit - lowerLimit)/3 and mid2 with upperLimit - (upperLimit - lowerLimit)/3.
- Initialize the variable cost1 with the cost of converting all array elements to mid1. You have to iterate the complete array to calculate cost1.
- Similarly, find cost2 by keeping mid2 as the target value of all elements in the array.
- If cost1 is less than cost2 then set upperLimit as mid2; otherwise, set lowerLimit as mid1.
- 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.
- Iterate index from 0 to N-1.
- Increment cost by an absolute difference of ARR[index] and target.
- Return the variable cost.
Similar problems