Find Duplicate Number

# Find Duplicate Number ## Difficulty Medium ## Tags `array`, `two pointers`, `cycle detection` ## Problem Statement Given an array of integers `nums` containing `n + 1` integers where each integer is in the range `[1, n]` inclusive, there is exactly **one repeated number**. Return this repeated number. You must solve the problem: - **Without** modifying the array `nums`. - Using only **O(1)** extra space. ## Constraints - 1 ≤ n ≤ 10⁵ - nums.length == n + 1 - 1 ≤ nums[i] ≤ n - All integers appear only once except for one which appears two or more times. ## Signatures ### Python ```python def find_duplicate(nums: List[int]) -> int: pass ``` ### Java ```java public class Solution { public int find_duplicate(List<Integer> nums) { return null; } } ``` ### Csharp ```csharp public class Solution { public int find_duplicate(IList<int> nums) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: int find_duplicate(vector<int> nums) { } }; ``` ### C ```c int find_duplicate(int* nums) { } ``` ### Ruby ```ruby def find_duplicate(nums) end ``` ### Perl ```perl sub find_duplicate { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def find_duplicate(nums: List[Int]): Int = { } } ``` ### Haskell ```haskell find_duplicate :: ... -> ... find_duplicate args = undefined ``` ### Clojure ```clojure (defn find_duplicate [nums] ) ``` ### Scheme ```scheme (define (find_duplicate nums) ) ``` ## Examples ### Example 1 **Input:** ``` nums = [1, 3, 4, 2, 2] ``` **Output:** ``` 2 ``` ### Example 2 **Input:** ``` nums = [3, 1, 3, 4, 2] ``` **Output:** ``` 3 ``` ### Example 3 **Input:** ``` nums = [2, 2, 2, 2, 2] ``` **Output:** ``` 2 ``` **Explanation:** The number 2 appears 5 times. ## Hints 1. Since values are in range [1, n] and we have n+1 elements, treat the array as a linked list. 2. Array index i points to index nums[i] (like a next pointer). 3. A duplicate means two indices point to the same next index → a cycle exists. 4. Use Floyd's Tortoise and Hare algorithm to find the cycle entrance. 5. Phase 1: Find the intersection point inside the cycle. 6. Phase 2: Find the entrance to the cycle (the duplicate).