A cooperative farm has built a row of n grain silos, numbered starting from 0. Because of how the row was constructed, silo i currently holds exactly 2*i + 1 units of grain — so the silos hold 1, 3, 5, 7, ... units of grain from left to right.
A worker can perform a transfer: pick any two silos (not necessarily adjacent) and move exactly one unit of grain from one into the other. Given only n, determine the minimum number of transfers needed so that every silo ends up holding the same amount of grain.
A single line containing one integer n, the number of silos.
Print a single integer: the minimum number of transfers needed to make all n silos hold equal amounts of grain.
Example 1
Input
3
Expected
2
Explanation
The silos hold 1, 3, 5 units; the total is 9 and the equalized target per silo is 9/3 = 3. Silo 2 has a surplus of 2 units above the target, which must move one unit at a time to silo 0 (which is 2 units short), for a total of 2 transfers.
Example 2
Input
6
Expected
9
Explanation
The silos hold 1, 3, 5, 7, 9, 11; the total is 36 and the equalized target is 6. The silos above target (7, 9, 11) have surpluses of 1, 3, and 5 respectively, summing to 9 units that must be transferred one at a time to the silos below target, for a total of 9 transfers.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →