# Make all 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).
Examples :

```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

Input  : arr[] = [4, 6]
Output : 2
We can change all its values to 5 with minimum cost,
|4 - 5| + |5 - 6| = 2
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

This problem can be solved by observing the cost while changing the target equal value, i.e. we will see the change in cost when target equal value is changed. It can be observed that, as we increase the target equal value the total cost decreases up to a limit and then starts increasing i.e. the cost graph with respect to target equal value is of U-shape and as cost graph is in U-shape, the ternary search can be applied to this search space and our goal is to get that bottom most point of the curve which will represent the smallest cost. We will make smallest and largest value of the array as the limit of our search space 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.
Please see below code for better understanding,

## C++

 `// C/C++ program to find minimum cost to ` `// make all elements equal ` `#include ` `using` `namespace` `std; ` ` `  `// Utility method to compute cost, when ` `// all values of array are made equal to X ` `int` `computeCost(``int` `arr[], ``int` `N, ``int` `X) ` `{ ` `    ``int` `cost = 0; ` `    ``for` `(``int` `i = 0; i < N; i++) ` `        ``cost += ``abs``(arr[i] - X); ` `    ``return` `cost; ` `} ` ` `  `// Method to find minimum cost to make all ` `// elements equal ` `int` `minCostToMakeElementEqual(``int` `arr[], ``int` `N) ` `{ ` `    ``int` `low, high; ` `    ``low = high = arr; ` ` `  `    ``// setting limits for ternary search by ` `    ``// smallest and largest element ` `    ``for` `(``int` `i = 0; i < N; i++) { ` `        ``if` `(low > arr[i]) ` `            ``low = arr[i]; ` `        ``if` `(high < arr[i]) ` `            ``high = arr[i]; ` `    ``} ` ` `  `    ``/* loop until difference between low and high ` `       ``become less than 3, because after that ` `       ``mid1 and mid2 will start repeating ` `    ``*/` `    ``while` `((high - low) > 2) { ` `        ``// mid1 and mid2 are representative array ` `        ``// equal values of search space ` `        ``int` `mid1 = low + (high - low) / 3; ` `        ``int` `mid2 = high - (high - low) / 3; ` ` `  `        ``int` `cost1 = computeCost(arr, N, mid1); ` `        ``int` `cost2 = computeCost(arr, N, mid2); ` ` `  `        ``// if mid2 point gives more total cost, ` `        ``// skip third part ` `        ``if` `(cost1 < cost2) ` `            ``high = mid2; ` ` `  `        ``// if mid1 point gives more total cost, ` `        ``// skip first part ` `        ``else` `            ``low = mid1; ` `    ``} ` ` `  `    ``// computeCost gets optimum cost by sending ` `    ``// average of low and high as X ` `    ``return` `computeCost(arr, N, (low + high) / 2); ` `} ` ` `  `// Driver code to test above method ` `int` `main() ` `{ ` `    ``int` `arr[] = { 1, 100, 101 }; ` `    ``int` `N = ``sizeof``(arr) / ``sizeof``(``int``); ` `    ``cout << minCostToMakeElementEqual(arr, N); ` `    ``return` `0; ` `} `

## Java

 `// JAVA Code for Make all array elements ` `// equal with minimum cost ` `class` `GFG { ` ` `  `    ``// Utility method to compute cost, when ` `    ``// all values of array are made equal to X ` `    ``public` `static` `int` `computeCost(``int` `arr[], ``int` `N, ` `                                  ``int` `X) ` `    ``{ ` `        ``int` `cost = ``0``; ` `        ``for` `(``int` `i = ``0``; i < N; i++) ` `            ``cost += Math.abs(arr[i] - X); ` `        ``return` `cost; ` `    ``} ` ` `  `    ``// Method to find minimum cost to make all ` `    ``// elements equal ` `    ``public` `static` `int` `minCostToMakeElementEqual(``int` `arr[], ` `                                                ``int` `N) ` `    ``{ ` `        ``int` `low, high; ` `        ``low = high = arr[``0``]; ` ` `  `        ``// setting limits for ternary search by ` `        ``// smallest and largest element ` `        ``for` `(``int` `i = ``0``; i < N; i++) { ` `            ``if` `(low > arr[i]) ` `                ``low = arr[i]; ` `            ``if` `(high < arr[i]) ` `                ``high = arr[i]; ` `        ``} ` ` `  `        ``/* loop until difference between low and high ` `           ``become less than 3, because after that ` `           ``mid1 and mid2 will start repeating ` `        ``*/` `        ``while` `((high - low) > ``2``) { ` `            ``// mid1 and mid2 are representative array ` `            ``// equal values of search space ` `            ``int` `mid1 = low + (high - low) / ``3``; ` `            ``int` `mid2 = high - (high - low) / ``3``; ` ` `  `            ``int` `cost1 = computeCost(arr, N, mid1); ` `            ``int` `cost2 = computeCost(arr, N, mid2); ` ` `  `            ``// if mid2 point gives more total cost, ` `            ``// skip third part ` `            ``if` `(cost1 < cost2) ` `                ``high = mid2; ` ` `  `            ``// if mid1 point gives more total cost, ` `            ``// skip first part ` `            ``else` `                ``low = mid1; ` `        ``} ` ` `  `        ``// computeCost gets optimum cost by sending ` `        ``// average of low and high as X ` `        ``return` `computeCost(arr, N, (low + high) / ``2``); ` `    ``} ` ` `  `    ``/* Driver program to test above function */` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``int` `arr[] = { ``1``, ``100``, ``101` `}; ` `        ``int` `N = arr.length; ` `        ``System.out.println(minCostToMakeElementEqual(arr, N)); ` `    ``} ` `} ` `// This code is contributed by Arnav Kr. Mandal. `

## Python3

 `# Python3 program to find minimum   ` `# cost to make all elements equal ` ` `  `# Utility method to compute cost, when ` `# all values of array are made equal to X ` `def` `computeCost(arr, N, X): ` ` `  `    ``cost ``=` `0` `    ``for` `i ``in` `range``(N): ` `        ``cost ``+``=` `abs``(arr[i] ``-` `X) ` `    ``return` `cost ` ` `  ` `  `# Method to find minimum cost to  ` `# make all elements equal ` `def` `minCostToMakeElementEqual(arr, N): ` ` `  `    ``low ``=` `high ``=` `arr[``0``] ` ` `  `    ``# Setting limits for ternary search  ` `    ``# by smallest and largest element ` `    ``for` `i ``in` `range``(N): ` `     `  `        ``if` `(low > arr[i]): low ``=` `arr[i] ` `        ``if` `(high < arr[i]): high ``=` `arr[i] ` ` `  ` `  `    ``# loop until difference between low and  ` `    ``# high become less than 3, because after  ` `    ``# that mid1 and mid2 will start repeating ` `    ``while` `((high ``-` `low) > ``2``): ` `     `  `        ``# mid1 and mid2 are representative  ` `        ``# array equal values of search space ` `        ``mid1 ``=` `low ``+` `(high ``-` `low) ``/``/` `3` `        ``mid2 ``=` `high ``-` `(high ``-` `low) ``/``/` `3` ` `  `        ``cost1 ``=` `computeCost(arr, N, mid1) ` `        ``cost2 ``=` `computeCost(arr, N, mid2) ` ` `  `        ``# if mid2 point gives more total ` `        ``# cost, skip third part ` `        ``if` `(cost1 < cost2): ` `            ``high ``=` `mid2 ` ` `  `        ``# if mid1 point gives more total  ` `        ``# cost, skip first part ` `        ``else``: ` `            ``low ``=` `mid1 ` `     `  ` `  `    ``# computeCost gets optimum cost by  ` `    ``# sending average of low and high as X ` `    ``return` `computeCost(arr, N, (low ``+` `high) ``/``/` `2``) ` ` `  `# Driver code ` `arr ``=` `[``1``, ``100``, ``101``] ` `N ``=` `len``(arr) ` `print``(minCostToMakeElementEqual(arr, N)) ` ` `  `# This code is contributed by Anant Agarwal. `

## C#

 `// C# Code to Make all array elements ` `// equal with minimum cost ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// Utility method to compute cost, when ` `    ``// all values of array are made equal to X ` `    ``public` `static` `int` `computeCost(``int``[] arr, ``int` `N, ` `                                             ``int` `X) ` `    ``{ ` `        ``int` `cost = 0; ` `        ``for` `(``int` `i = 0; i < N; i++) ` `            ``cost += Math.Abs(arr[i] - X); ` `        ``return` `cost; ` `    ``} ` ` `  `    ``// Method to find minimum cost to ` `    ``// make all elements equal ` `    ``public` `static` `int` `minCostToMakeElementEqual(``int``[] arr, ` `                                                    ``int` `N) ` `    ``{ ` `        ``int` `low, high; ` `        ``low = high = arr; ` ` `  `        ``// setting limits for ternary search by ` `        ``// smallest and largest element ` `        ``for` `(``int` `i = 0; i < N; i++) { ` `            ``if` `(low > arr[i]) ` `                ``low = arr[i]; ` `            ``if` `(high < arr[i]) ` `                ``high = arr[i]; ` `        ``} ` ` `  `        ``/* loop until difference between low and high ` `        ``become less than 3, because after that ` `        ``mid1 and mid2 will start repeating ` `        ``*/` `        ``while` `((high - low) > 2) { ` `             `  `            ``// mid1 and mid2 are representative array ` `            ``// equal values of search space ` `            ``int` `mid1 = low + (high - low) / 3; ` `            ``int` `mid2 = high - (high - low) / 3; ` ` `  `            ``int` `cost1 = computeCost(arr, N, mid1); ` `            ``int` `cost2 = computeCost(arr, N, mid2); ` ` `  `            ``// if mid2 point gives more total cost, ` `            ``// skip third part ` `            ``if` `(cost1 < cost2) ` `                ``high = mid2; ` ` `  `            ``// if mid1 point gives more total cost, ` `            ``// skip first part ` `            ``else` `                ``low = mid1; ` `        ``} ` ` `  `        ``// computeCost gets optimum cost by sending ` `        ``// average of low and high as X ` `        ``return` `computeCost(arr, N, (low + high) / 2); ` `    ``} ` ` `  `    ``/* Driver program to test above function */` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``int``[] arr = { 1, 100, 101 }; ` `        ``int` `N = arr.Length; ` `        ``Console.Write(minCostToMakeElementEqual(arr, N)); ` `    ``} ` `} ` ` `  `// This code is contributed by nitin mittal `

## PHP

 ` ``\$arr``[``\$i``]) ` `            ``\$low` `= ``\$arr``[``\$i``]; ` `        ``if` `(``\$high` `< ``\$arr``[``\$i``]) ` `            ``\$high` `= ``\$arr``[``\$i``]; ` `    ``} ` ` `  `    ``/* loop until difference between  ` `    ``low and high become less than 3, ` `    ``because after that mid1 and mid2  ` `    ``will start repeating */` `    ``while` `((``\$high` `- ``\$low``) > 2)  ` `    ``{ ` `        ``// mid1 and mid2 are representative  ` `        ``// array equal values of search space ` `        ``\$mid1` `= ``\$low` `+ (``floor``(``\$high` `- ``\$low``) / 3); ` `        ``\$mid2` `= ``\$high` `- (``\$high` `- ``\$low``) / 3; ` ` `  `        ``\$cost1` `= computeCost(``\$arr``, ``\$N``, ``\$mid1``); ` `        ``\$cost2` `= computeCost(``\$arr``, ``\$N``, ``\$mid2``); ` ` `  `        ``// if mid2 point gives more total  ` `        ``// cost, skip third part ` `        ``if` `(``\$cost1` `< ``\$cost2``) ` `            ``\$high` `= ``\$mid2``; ` ` `  `        ``// if mid1 point gives more  ` `        ``// total cost, skip first part ` `        ``else` `            ``\$low` `= ``\$mid1``; ` `    ``} ` ` `  `    ``// computeCost gets optimum cost by  ` `    ``// sending average of low and high as X ` `    ``return` `computeCost(``\$arr``, ``\$N``, (``\$low` `+  ` `                                  ``\$high``) / 2); ` `} ` ` `  `// Driver Code ` `\$arr` `= ``array``( 1, 100, 101 ); ` `\$N` `= sizeof(``\$arr``) / sizeof(``\$arr``); ` `echo` `minCostToMakeElementEqual(``\$arr``, ``\$N``); ` ` `  `// This code is contributed by nitin mittal. ` `?> `

Output :

```100
```

Time Complexity : O (n Log n)

## tags:

Arrays Searching Arrays Searching