Make Array Elements Equal

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
11 upvotes
Asked in companies
CIS - Cyber InfrastructureMakeMyTrip

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3
1 8 19
4
2 17 26 11
Sample Output 1:
18
30
Explanation:
In test case 1
We can change all element’s value to 8 with cost |1-8| + |19 - 8| = 18. The value 18 is the minimum cost to make all values in the array equal. Hence, the answer is 18.

In test case 2 
We can change all element’s value to 11 with cost |2 - 11| + |17 - 11| + |26 - 11| = 30. The value 30 is the minimum cost to make all values in the array equal. Hence, the answer is 30.
Sample Input 2:
1
3
1 100 101
Sample Output 2:
100
Hint

Try to use the brute force approach to find the minimum cost.

 

Approaches (2)
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.
Time Complexity

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))).

Space Complexity

O(1).

 

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

Code Solution
(100% EXP penalty)
Make Array Elements Equal
Full screen
Console