My approach is of complexity O (kn), where k = range (min (array) to max (array)) (inclusive) and n = size of the array. It passed all the test cases.
REMEMBER: The point of convergence doesn't HAVE to be an element from the array. It can be any number in the range of min to max, so I applied exhaustive search.

def get_optimal (array, size, pivot, op1, op2):
inc = dec = cost = 0
for i in array:
if (i < pivot):
inc += (pivot - i);
elif (i > pivot):
dec += (i - pivot);

if (dec > inc):  
    return (float ('inf'));  

cost += dec * op1;  
inc -= dec;  
cost += (inc * op2);  
return (cost);  

size, op1, op2 = [int (i) for i in input ().split ()];
array, optimal = [int (i) for i in input ().split ()], float ('inf');

for i in range (min (array), max (array) + 1):
temp = get_optimal (array, size, i, op1, op2);
optimal = temp if optimal > temp else optimal;
print (optimal);

Hi I am trying to solve this by first sorting the elements and consider each element as median ( the number to which we should convert all other number) and trying to get the coins for other elements to convert to the median and finally will display the minimum coins that we get.

First trying to calculate the difference between the median and its right side(elements that are higher than the median) elements. Then add the difference. Getting this sum of difference to caluclate the cost for performing the first operation. Cost will be directly multiply the sum of difference with the value k.

Then getting the sum of difference on the left side. This will be used to calculate to perform second operation. I'll subract the sum of median's right side difference from left side as we already used them for performing the first opertaion. The cost for performing second operation will be remaining difference multiplied by l.

The sum of the above two will give the answer. Similarly will do the steps for all elements as median then will display the minimum value as the cost. What am I missing in this.

int upperMedianDiff = 0; for (int i = medianIndex + 1; i < n; i++) { if (elementsList.get(i) != median) { upperMedianDiff += (elementsList.get(i) - median); } } int lowerMedianDiff = 0; for (int i = 0; i < medianIndex; i++) { if (elementsList.get(i) != median) { lowerMedianDiff += (median - elementsList.get(i)); } } if (upperMedianDiff <= lowerMedianDiff) { tempAns += (upperMedianDiff * k); tempAns += (lowerMedianDiff - upperMedianDiff) * l; } if (tempAns != 0) { ans = Math.min(ans, tempAns); }

How can anyone solve this problem in less then 3 or even 5 mins. It takes me more than that just to read and understand the requirments. Then, I think about the approach then I start coding. Can anyone explain me how those top 10 could solve this problem, in less than 5 mins?!!

In editorial problem setter talked about 'size' h. What did he mean by h? Size of array is n, so what is 'h'

What's the approach to solve this problem?