i have been trying to solve this question since the last 2 days but am not able to get a good algo for this problem.can someone help me out in this one.?.
How much have you gone forward in this problem? Where are you getting stuck?
Please share information on what you have found till now. 
Well, this problem isn’t that hard, but you need focus on right things.
You’re trying to divide candies on piles and each pile should contain some candies. For each missing candy you obtain some anger and you want to minimaze total amount of anger. First logical question is: “Is better to keep one pile full and other almost empty, or trying to balanced it, so each pile missing some number of candies?”
The answer is simple, when you write it down. Imagine two piles. First pile is missing x candies, second is missing x+k candies for some positive k. Amount of anger is x^2 + (x+k)^2 = 2(x^2) + 2xk + k^2.
Now take one candy from bigger pile (with only x candies missing) and take it on second pile. You missing x+1 candies on first and x+k-1 candies on second pile. The amount of anger is (x+1)^2 + (x+k-1)^2 and when we multiply brackets it’s equal to 2(x^2) + 2xk + k^2 -2k + 2. So total amount of anger decreased, when we balanced number of missing candies on piles.
So solution is clear now. We want to divide candies in such manner, that on each pile number of missing candies is equal (or may differ by 1).
The easiest and the fastest way to find number of missing candies on each pile is use binary search. If we want r candies missing everywhere, we should find out, if sum of all piles minus r for each of them (maybe even less than r, if pile is not big enough) is less or equal than M - total number of candies.
When we find optimal (as small as possible) value of r just fairly distribute all candies between piles. And you’ve got it
I think, that hardest part is to realize, that you want to balance number of missing candies on each pile. After this, it’s pretty easy.
1 Like