🌟Find duplicate Element in the array🌟
Tags: tutorial, todayilearned, discuss, programming
Published: 2021-03-20 09:02:37

**Question :** 

Given an array of integers `nums` containing `n + 1` integers where each integer is in the range `[1, n]` inclusive.

There is only **one repeated number** in `nums`, return *this repeated number*.

**Example 1:**

```
Input: nums = [1,3,4,2,2]
Output: 2
```

**Logic:**

1. Naive Approach :
    - Take input as array
    - run 1 loop from i to arr . length - 2 location
    - run 2nd loop from i to arr . length - 1 location
    - if arr[ i ] = arr[ j ] then break out of the loop and return the arr [ i ] or arr[ j ]

2. Sorting : 
    - Take input as array
    - sort the array using library function
    - run a loop from i to arr . length - 2.
    - and check if  arr[ i ] = arr[ i+1 ]. If yes then return arr [ i ]

3. Extraspace : 
    - Take the input as array
    - sort the array using library function
    - create an extra[ ] array of arr.length size
    - run the loop from i to arr.length -1
    - check if extra [ arr [ i ] ] = 0. if yes then make extra [ arr [ i ] ] = 1 and if no then return arr [ i ]
4. Linked List / Rabbit and Tortoise method:
    - Take input as array
    - create a linked list and run a loop from i = 0 to i = arr . length
    - make i = arr [ i ] and add arr [ i ] to linked list ( as shown in the code )
    - take two pointers slow and fast. move slow by one step and fast by two steps
    - whenever they will meet put fast on the first element
    - and now move fast by one and slow by one until they both meet at a point
    - return slow.

```java
import java.util.*;

public class Solution{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int arr[] = new int[n];
        for(int i = 0; i < arr.length; i++){
            arr[i] = sc.nextInt();
        }

        //This is Naive approach with Complexity O(N^2)
        int repeat = 0;
        for(int i = 0; i < arr.length-1; i++){
            for(int j = i+1; j < arr.length; j++){
                if(arr[i] == arr[j]){
                    repeat = arr[i];
                    break;
                }
            }
        }
        System.out.println("Repeated element through naive approach is: "+repeat);

        //This is Sort and Two pointer approach with complexity  (O(N*logN)+ O(N))
        int repeat2 = 0;
        Arrays.sort(arr);
        for(int i = 0; i < arr.length-1; i++){
            if(arr[i] == arr[i+1]){
                repeat2 = arr[i];
                break;
            }
        }
        System.out.println("Repeated element through sort + two pointer approach is: "+repeat2);

        //This is Sort and extra space approach
        int repeat3 = 0;
        int extra[] = new int[n];
        for(int i = 0; i < extra.length; i++){
            extra[i] = 0;
        }
        Arrays.sort(arr);

        for(int i = 0 ; i < arr.length; i++ ){
            if(extra[arr[i]] != 0){
                repeat3 = arr[i];
                break;
            }else{
                extra[arr[i]] = 1;
            }
        }
        System.out.println("Repeated element through sort + extra space is: "+repeat3);

        //This is Linked list with tortoise and rabbit method
        int repeat4 = 0;
        LinkedList<Integer> li = new LinkedList<>();
        for(int i = 0; i < arr.length; i++){
            i = arr[i];
            li.add(arr[i]);
        }
        Integer nums[] = li.toArray(new Integer[li.size()]);
        int slow = nums[0];
        int fast = nums[0];
        do{
            slow = nums[slow];
            fast = nums[nums[fast]];
        }while(slow != fast);

        fast = nums[0];
        while(slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }

        repeat4 = slow;
        System.out.println("Repeated elements through linked list approach is: "+repeat4);
     }
}
```