# Tortoise & Haire cycle detection algorithm

• O(n) time O(1) space solution -

``````public class Solution {
public static int findDuplicate(int[] nums) {
//using Tortoise & Hair algorithm by Donald Knuth to find cycle in a sequence.
//This algorithm also called Floyd's cycele detection algorithm
int n = nums.length;
int tortoise = n;
int hair = n;

do{
tortoise = nums[tortoise-1];
hair = nums[nums[hair-1]-1];
} while(hair != tortoise);

//find the starting point of the cycle
//int mu = 0;
tortoise = n;
while(hair != tortoise){
tortoise = nums[tortoise-1];
hair = nums[hair-1];
//mu++;
}

}
}``````

• I am not sure if the algorithm handles the case where nums[n-1] = n.

Could anyone help clarify?

• In that case, n must be the duplicated number.

• this case can be handled. There are two situations: situation A: the n is not the duplicated num, then it shall be isolated, neither slow or fast pointer can visit it, e.g 3, 2, 1, 1. So it will not impact the algorithm. situation B: n is the duplicated num, e.g 3, 2, 2, 1, for sure it can be solved by the algorithm

• it definitely doesn't work with [1,2,2,4].

• This test case is incorrect according to the question.

• The input must meet the requirement that the size of the largest element in the array should be less than the length of array. For example, [1, 2, 2, 3] the length is 4, the largest element should be less than 4 which is 3. So [1, 2, 2, 4] is a invalid input according to the question.

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