Let ~S~ be the sum of all wishes. Imagine that each child was given as many candies as it wants, and now they have to be taken away, leaving ~M~ candies in total. That is, we have to take ~S-M~ candies away.

Since the sum of the numbers of candies that the children will be missing is constant (equal to ~S-M~), and we wish to minimize the sum of squares of those numbers, a key observation is that the numbers should be "as equal as possible". More precisely, it is possible to prove mathematically (using the inequality of arithmetic and geometric means) that the sum of squares of positive numbers, with a fixed sum, is minimal when they are equal.

Let ~K~ be the remaining number of candies that need to be taken away (the starting value of ~K~ is ~S-M~). Our goal is to, if possible, take away an equal number of candies from each child, specifically ~K/N~. If this is not possible, the number of candies taken away should be as close as possible to ~K/N~.

If the child that wants the smallest amount of candies has at least ~K/N~ candies, we will be able to fulfill the goal by taking ~K/N~ candies away from it, thus reducing the problem to the remaining ~N-1~ children (by decrementing ~N~, calculating the new value of ~K~, and processing the child with the next smallest wish). On the other hand, if the observed child has less than ~K/N~ candies, preventing us from taking that many from it, we will take as many as we can, i.e. all the candies it was given, and proceed to process the remaining children.

In the end, we can just output the sum of squared numbers of candies taken away from the children. The complexity of the described algorithm is linear, but it requires first sorting children's wishes into a nondecreasing sequence, resulting in the total complexity of ~\mathcal O(N \log N)~.

It is also possible to solve this problem using binary search, however this solution is left as an exercise for the reader.