Given an array of elements, you can only increase array elements. The cost of an operation is the amount of increment made per array element. For a given H, make any H elements of the array equal with minimum cost. For example, if N=6, H=4 and the array is [2, 3, 5, 6, 4, 4], changing it to [4, 4, 5, 6, 4, 4] has a cost of (4-2 + 4-3 = 3). If N=6, H=3 and the array is [2, 3, 5, 6, 4, 4], changing it to [2, 4, 5, 6, 4, 4] has a cost of (4-3 = 1). What is the optimal O(N) solution?

Question

Accepted Answer

Minimize cost to make H elements of an array equal by only increasing their values.

Identify the target value H that elements should be increased to.
Calculate the cost for each element that needs to be increased to H.
Select the H smallest costs to minimize total cost.
Example: For array [2, 3, 5, 6, 4, 4] and H=4, costs are [2, 1, 0, 0, 0, 0]. Total cost = 3.
Optimal complexity is achieved by sorting or using a min-heap to find the smallest costs.

Snapdeal Software Developer interview questions & answers

Popular interview questions of Software Developer