The simplified problem description is as follows.
A teacher has n packets of candies of varying sizes. The problem is to find the number of candies to be moved from one packet to others to get equal number of candies in all packets.
For example consider 5 packets of candies having {1, 2, 3, 4, 5} candies. the number of candies to be moved are 3.
Explanation: Take out 1 candy from 4 and add it to 2, and take out 2 from 5 and add it to 1. Now every packet contains 3 candies.
There are cases where we can not make candies in each packet equal by moving any number of candies. We have to output -1 in that case.
The approach to solve this problem is as follows.
First check if we can equal the packets in any way. How can we do this?
Sum all numbers and see if it is properly divided by the number of candies (integer average is possible). If it is possible we can proceed to divide the candies to make them equal.
The next problem is to find out the number of candies to be moved. Find the sum of all excess candies in each packet by comparing them with average number of candies.
This algorithm runs in O(n) time and O(1) space complexity.
Here is the accepted C++ code for this problem.