Find the Duplicate Number
Medium · Arrays & Strings · about 25 minutes
Asked at Google, Amazon, Microsoft, Bloomberg.
An array nums holds n + 1 integers, each in the range [1, n]. Exactly one value is repeated (possibly more than twice). Return the repeated value without modifying the array and using only O(1) extra space.