[INTERESTING] MAKE PILES OF EQUAL HEIGHT

Given N piles of coins and the number of coins in each pile, your job is to make all piles have same number of coins. You can add or remove one single coin from a pile at a time. Removing or adding a coin affects only a single pile. Also adding a coin to a pile costs c1 and removing a coin from a pile costs c2. What is the minimum cost to make the coins in all the piles equal assuming you have infinite number of coins which you can use to add on any pile ?

Note: A Coin can be removed from a pile only when the pile has at least one coin.

for eg.

n = 3 
coins in each pile = [1,5,10]
c1 = 1, c2 = 1;
ans = 9

How will you solve this problem ?

Can u please link the problem :slight_smile:

do u have a link???

Sorry, I don’t have the link, we can discuss the logic which is more important.

I think ternary search may be applied on this problem

This seems to be binary search question.
Final pile size will lie between min and max number of coins in all the piles.

  1. consider mid as final size of all piles.
  2. calculate the cost of insertion and deletion
  3. based on costOfInsertion and costOfDeletion reduce the search space.
  4. for each pass calculate the min total cost

time complexity: O(nlog n)

i would consider binary search as solution for this problem