## DEV Community

Kaiwalya Koparkar

Posted on

# 🌟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;
for(int i = 0; i < arr.length; i++){
i = 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);
}
}
``````