# solution with explanation

• ``````public class Solution {
public int findDuplicate(int[] nums) {
int slow = nums[0];
int fast = nums[nums[0]];
// mu --- first node of repetition
// lam --- length of the loop
while (slow != fast) {  //x_{i} = x_{2i} = x_{i + k * lam} ==> i = k * lam
slow = nums[slow];
fast = nums[nums[fast]];
}

slow = 0;
// slow is at x_{0}, fast is at x_{k * lam}
// x_{j} = x_{j + k * lam}  ==> j = mu for any j >= mu
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
// slow and fast are both at mu
return slow;
}
}
``````

This page gives a quite clear explanation of the `Floyd's cycle-detection algorithm`. Here is the principal:

• The position where the two pointers meet must satisfy this relation: `x_{i} = x_{i + k * lambda}` where `x_{i}` is the position representation for the slower pointer and `x_{i + k * lambda}` is the position representation for the faster pointer. `k` is a constant and `lambda` is the length of the loop.
• When the speed of the faster pointer is twice of the speed of the slower (that is, `i + k * lambda = 2i`), `i = k * lambda`. This indicates that slower and faster pointers meet at a `k * lambda` away from the origin, denote this distance as `v`. That is, `v = k * lambda`.
• After knowing `v`. We relocate two pointers, one at origin and the other at `v`. That is, they are `v` apart. Move them with the same speed. So one is at `x_{j}` and the other is at `x_{j + v}`. Remember `v = k * lambda`, `x_{j} = x_{j + k *lambda}` for any `j >= mu`, where `mu` is the entry point of the loop (i.e. they are constant cycles apart).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.