Given an array of n+1 integers (each of which is selected from the set of numbers from 1 to n), write an algorithm that finds any duplicate. For example, you might be given arrays like so: [2, 3, 3, 1, 1], [4, 1, 3, 2, 4], and [2, 2, 2, 2, 2]. All of them select from the set {1, 2, 3, 4}.
[Solution]