Find the Duplicate Number in an Array

Problem: Given an array of n+1 integers where each integer is between 1 and n (inclusive), and exactly one number is duplicated (possibly multiple times), find the duplicate number without modifying the array and using O(1) extra space.

Constraints: Array values in range [1, n], array length n+1, exactly one repeated value.

Example: [1,3,4,2,2] -> duplicate is 2.

Approach: Treat the array as a function mapping index -> value, forming an implicit linked list; the duplicate creates a cycle. Use Floyd's Cycle Detection (tortoise and hare) to find the cycle entry point, which corresponds to the duplicate number. O(n) time, O(1) space.