Minimizing steps to distribute in a candies in a circle
algorithm, complexity-theory, optimization
Solution
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.
Problem
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 - (-3, -2, 4, 1) - (-2, -2, 4, 0) - (-2, -1, 3, 0) - (-2, 0, 2, 0) - (-2, 1, 1, 0) - (-2, 2, 0, 0) - (-1, 1, 0, 0) - ( 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?