Daily bit(e) of C++ | Minimum cost to equal array
Daily bit(e) of C++ #77, Common interview problems: Minimum cost to reach an equal array
Today we will look at a common C++ interview problem: Minimum cost to reach an equal array
Given two arrays (numbers and costs) of positive integers, determine the minimum cost to adjust the numbers array so that all elements are of the same value.
The cost of adjusting each element by one is the corresponding element in the costs array.
For example, for the numbers array {1,3,5,2} and the costs array {2,3,1,14}, the result is 8. The cheapest target array is {2,2,2,2}, which means that we will have to adjust the elements 1 and 3 once, costing 1*2+1*3 and the element 5 three times, costing 3*1, for a total of 8.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/dedx8Yd68.
Solution
To solve this problem, we need a small bit of mathematical knowledge.
Let’s first consider a single element of the array. The function representing the cost to adjust this element is convex; that is, the minimum of the function is when we do not adjust this element at all and then grows on both sides monotonically.
The mathematical piece of trivia is that a sum of convex functions is also convex.
We can use a binary search to find a minimum of a convex function. In this case, the function is the total cost, which we will (due to the binary search) calculate a total of logk times, where k is the domain of the values in the numbers array (i.e. max(numbers)-min(numbers)). Since our cost function is a simple linear reduction, we end up with a total complexity of O(n*logk).
