I thought my solution is quite "brute", are there any other solutions?
And I have to say it is a really good problem for sufficient samples and a clear statement.

And where is your solution?