Question

• https://leetcode.com/problems/find-the-duplicate-number/

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

Approach

• Cycle detection

Solution

``` class Solution { public int findDuplicate(int[] nums) { // Find the intersection point of the two runners. int tortoise = nums[0]; int hare = nums[0]; do { tortoise = nums[tortoise]; hare = nums[nums[hare]]; } while (tortoise != hare);

// Find the "entrance" to the cycle.
tortoise = nums[0];
while (tortoise != hare) {
  tortoise = nums[tortoise];
  hare = nums[hare];
}

return hare;   } };```