Find the single number that duplicates one or more times

Find the single number that duplicates one or more times in an array in O(1) space and O(n) time without modifying the array

Note:
You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

Note that, we can solve this problem by constructing a graph by considering each position as a vertex and value at an index as the pointer (or index) to the connecting vertex. In this way if there is no repeating element then the graph will be a simple non-cyclic path. But if there is repeating element then we will have cycles in the path. There is a very nice O(n) solution to find cycles in graphs.

Tortoise and Hair Cycle detection algorithm (pr Floyd’s cycle-finding algorithm)
(From wiki)
Let S be any finite set, ƒ be any function from S to itself, and x0 be any element of S. For any i > 0, let xi = ƒ(xi−1). Let μ be the smallest index such that the value xμ reappears infinitely often within the sequence of values xi, and let λ (the loop length) be the smallest positive integer such that xμ = xλ+μ. The cycle detection problem is the task of finding λ and μ.

The figure shows a function ƒ that maps the set S = {0,1,2,3,4,5,6,7,8} to itself. If one starts from x0 = 2 and repeatedly applies ƒ, one sees the sequence of values

2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ….
The cycle in this value sequence is 6, 3, 1.

Floyd’s cycle-finding algorithm, also called the “tortoise and the hare algorithm”, alluding to Aesop’s fable of The Tortoise and the Hare, is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds.

The key insight in the algorithm is that, for any integers i ≥ μ and k ≥ 0, xi = xi + kλ, where λ is the length of the loop to be found and μ is the index of the first element of the cycle. In particular, whenever i = kλ ≥ μ, it follows that xi = x2i. Thus, the algorithm only needs to check for repeated values of this special form, one twice as far from the start of the sequence as the other, to find a period ν of a repetition that is a multiple of λ. Once ν is found, the algorithm retraces the sequence from its start to find the first repeated value xμ in the sequence, using the fact that λ divides ν and therefore that xμ = xμ + v. Finally, once the value of μ is known it is trivial to find the length λ of the shortest repeating cycle, by searching for the first position μ + λ for which xμ + λ = xμ.

The algorithm thus maintains two pointers into the given sequence, one (the tortoise) at xi, and the other (the hare) at x2i. At each step of the algorithm, it increases i by one, moving the tortoise one step forward and the hare two steps forward in the sequence, and then compares the sequence values at these two pointers. The smallest value of i > 0 for which the tortoise and hare point to equal values is the desired value ν.

	//find the single number that duplicates one or more times in an array in O(1) space and O(n) time without modifying the array
	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 cycle 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 and distance from the front, mu
        int mu = 0;
        tortoise = n;
        while(hair != tortoise){
            tortoise = nums[tortoise-1];
            hair = nums[hair-1];
            mu++;
        }
        
        //find the min length lambda of the cycle
        int lambda = 1;
        hair = nums[tortoise-1];
        
        while(hair != tortoise){
        	hair = nums[hair-1];
        	lambda++;
        }
        
        System.out.println("mu : "+mu+" lambda: "+lambda);
        
        return tortoise;
    }

Detecting and Removing Cycle in Linked List
In case of linked list,

f(x) = x.next.

Note that if the cycle begins at mth node from head and cycle length is n then slow and fast pointer will meet at a node k distance from the cycle start node. That is the pointers will meet at (m+k)th node from head. Let’s by the time slow reaches the meet point the fast pointer traverse the cycle c1 times and slow pointer by c2 times. Then ,

2*(m+c1*n+k) = (m+c2*n+k)
=> m+k = (c2-2c1)*n;
=> m+k is multiple of n

So if we start moving both pointers again at same speed such that slow begins from head node of linked list and fast begins from meeting point, then when slow pointer reaches beginning of cycle in the linked list (has made m steps), the fast pointer would have made also moved m steps as they are now moving same pace. Since m+k is a multiple of n and fast starts from k, they would meet at the beginning.

public void removeCycle(ListNode head){
	ListNode slow = head;
	ListNode fast = head.next;
	
	while(fast != null && fast.next != null){
		if(slow == fast){
			break;
		}
		slow = slow.next;
		fast = fast.next.next;
	}
	
	if(slow == fast){
		slow = head;
		while(slow != fast.next){
			slow = slow.next;
			fast = fast.next;
		}
		
		fast.next = null;
	}
}