Find the single number that duplicates one or more times

Find the single number that duplicates one or more times - Algorithms and Problem SolvingAlgorithms and Problem Solving

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(n^2).
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.

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.

 //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

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;
 }
}

Read full article from Find the single number that duplicates one or more times - Algorithms and Problem SolvingAlgorithms and Problem Solving