suppose the array is

index: 0 1 2 3 4 5

value: 2 5 1 1 4 3

first subtract 1 from each element in the array, so it is much easy to understand.

use the value as pointer. the array becomes:

index: 0 1 2 3 4 5

value: 1 4 0 0 3 2

Second if the array is

index: 0 1 2 3 4 5

value: 0 1 2 4 2 3

we must choose the last element as the head of the linked list. If we choose 0, we can not detect the cycle.

Now the problem is the same as find the cycle in linkedlist!

```
public int findDuplicate(int[] nums) {
int n = nums.length;
for(int i=0;i<nums.length;i++) nums[i]--;
int slow = n-1;
int fast = n-1;
do{
slow = nums[slow];
fast = nums[nums[fast]];
}while(slow != fast);
slow = n-1;
while(slow != fast){
slow = nums[slow];
fast = nums[fast];
}
return slow+1;
}
```

One condition is we cannot modify the array. So the solution is

```
public int findDuplicate(int[] nums) {
int n = nums.length;
int slow = n;
int fast = n;
do{
slow = nums[slow-1];
fast = nums[nums[fast-1]-1];
}while(slow != fast);
slow = n;
while(slow != fast){
slow = nums[slow-1];
fast = nums[fast-1];
}
return slow;
}
```