🌟Find duplicate Element in the array🌟

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.

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