Let ~X~ be the lowest possible envy level, and ~Mx~ the largest number of marbles of a single colour. It is not difficult to show that for all numbers ~Y~ between ~X~ and ~Mx~, inclusive, we can attain an envy level of ~Y~.

It follows that binary search can be used to find the requested solution ~X~. We can begin with the lower bound of ~1~ and upper bound of ~Mx~. In each step, for a number ~Y~ halfway between the current bounds, we can check whether it is larger or smaller than ~X~, i.e. whether it is possible to attain an envy level of ~Y~.

How can we check that? We can iterate over all colours and divide each of them into as many portions of size ~Y~ as possible. More precisely, if we have ~K~ marbles of a given colour, we will make ~K~ div ~Y~ portions of size ~Y~, as well as one more portion if we have any leftover marbles (if ~Y~ does not divide ~K~). After we have distributed all colours in the manner above, if the total number of portions is at most ~N~, we have successfully attained an envy level of ~Y~, concluding ~Y \ge X~. Otherwise, we have to conclude ~Y < X~, since we have made too many portions, which means that at least one child must get more than ~Y~ marbles.