Problem solving with programming: Problem of candies: SPOJ
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.
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.
Read full article from Problem solving with programming: Problem of candies: SPOJwhile (true){int n;cin >> n;if( n == -1 )break;vector<int> candies(n);int i;long long sum = 0;for( i = 0; i < n; i++ ){cin >> candies[i];sum += candies[i];}if( sum % n == 0 ){long long avg = sum/n;long long r = 0;for( i = 0; i < n; i++ ){if( candies[i] > avg ){r += candies[i]-avg;}}cout << r << endl;}else{cout << "-1" << endl;}}