Minimizing steps to distribute in a candies in a circle

Question

There are n children in a circle. Each of them has some candies (may be negative, positive or zero). They can give at a time a single candy to their neighbors. The end result is that they all should have zero candies in minimum steps.

Suppose we have 4 children with (-4, -2, 4, 2) candies then the sequence will be

1. (-3, -2, 4, 1)
2. (-2, -2, 4, 0)
3. (-2, -1, 3, 0)
4. (-2, 0, 2, 0)
5. (-2, 1, 1, 0)
6. (-2, 2, 0, 0)
7. (-1, 1, 0, 0)
8. ( 0, 0, 0, 0)

This is one possible answer, I have to find minimum number of steps.

• Loop 1: find if a neighbor has positive candies,then give it to the neighbor with negative candies till number of candies is equal to zero and add the number of candies given to sum.

• Loop 2: find if a neighbors' neighbour has positive candies, then give it to the neighbor with negative candies till number of candies is equal to zero and add 2 (the number of candies given to sum).

• and so on.

The complexity of my solution is causing a TLE. What can I do to reduce the complexity?

Answer 1

I don't think you need to loop round in detail. Write the number of candies in each place as X1, X2, X3, X4. Suppose that X1 receives k candies from its left (that is, for X4). After this it has X1+k candies, so it must pass this to its right. Then X2 will have X1 + X2 + k candies, so it must pass this to its right. X3 will then have X1 + X2 + X3 + k candies, so it must pass this to X4. We know X4 passed k candies, and this checks (assuming that X1 + X2 + X3 + X4 = 0 and if it doesn't there is no solution).

This takes |k| + |X1 + k| + |X1 + X2 + k| + |X1 + X2 + X3 + k| steps, so if we guess k we know how many steps to take. What is the best value of k? If we increase k we increase the sum if there are more +ve terms X1 + X2 + ... k, and decrease if there are more -ve terms. So the best value of k is one in which exactly half of the terms |k|, |X1 + k|.. are +ve and exactly half -ve because if this is not the case we can either increase or decrease k to make things better - the value of k to choose is - the median of 0, X1, X1 + X2, X1 + X2 + X3.

I have stated this for the n=4 case of your example but I hope that you can work out the answer for general n from this.