# Find the Duplicate Element

Difficulty Level Medium
Array Binary Search Two PointerViews 4479

Given an array of integers of size n+1 where each element of the array is between 1 and n (inclusive), there is one duplicate element in the array, find the duplicate element.

## Brute force method – Approach 1 for Find the Duplicate Element

For every ith element run a loop on the given array from (i+1) to n and check if the ith element is present in it or not.

### Complexity Analysis for finding the duplicate element

Space complexity: O(1)

Time complexity: O(n^2)

### C++ program

```#include<bits/stdc++.h>
using namespace std;

int findDuplicate(int a[],int n){
for(int i=0;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(a[i]==a[j]){            // Duplicate element found
return a[i];
}
}
}
return -1;                         // invalid input
}

int main(){
int n;
cin>>n;
int a[n+1];
for(int i=0;i<n+1;i++){
cin>>a[i];
}
int ans = findDuplicate(a,n);
cout<<"Duplicate element is: "<<ans;
}
```
```6
6 5 1 2 6 3 4
```
`Duplicate element is: 6`

### JAVA program

```import java.util.*;
public class Main
{
public static int findDuplicate(int[] a,int n){
for(int i=0;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(a[i]==a[j]){ // Duplicate element found
return a[i];
}
}
}
return -1; // invalid input
}
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n+1];
for(int i=0;i<n+1;i++){
a[i] = sc.nextInt();
}
int ans = findDuplicate(a,n);
System.out.println("Duplicate element is: "+ans);
}
}

```
```5
1 4 2 3 3 5```
`Duplicate element is: 3`

## Using Hashing – Approach 2

### Algorithm

Step1: Create a hashmap to store the frequency of each element.

Step2: Traverse the array ones and update the frequency of each element in the hashmap.

Step 3: Traverse the hashmap, and return the element with frequency 2.

### Complexity Analysis for finding the duplicate element

Space Complexity: O(n), we are using a extra memory in the for of hash which which will have a size of n in the worst case.

Time complexity: O(n), we need to traverse the array for once to calculate the frequency of each number. And then traverse the map to find the element with frequency more than 1.

### C++ Program

```#include<bits/stdc++.h>
using namespace std;

int findDuplicate(int a[],int n){
unordered_map<int,int> u;
for(int i=0;i<=n;i++){
if(u.find(a[i])==u.end()){
u.insert(make_pair(a[i],1));
}
else{
u[a[i]]++;
}
}
for(auto it=u.begin();it!=u.end();it++){
if(it->second == 2){            // the element is duplicate if it's frequency is more that 1
return it->first;
}
}
return -1;                 // in case of invalid input
}

int main(){
int n;
cin>>n;
int a[n+1];
for(int i=0;i<n+1;i++){
cin>>a[i];
}
int ans = findDuplicate(a,n);
cout<<"Duplicate element is: "<<ans;
}
```
```5
5 2 4 1 2 3
```
`Duplicate element is: 2`

## Using Xor properties – Approach 3 for Find the Duplicate Element

a^a = 0 and a^0 = a

### Algorithm

Step 1: Find the xor of 1 to n and store it in variable X.

Step 2: Find the xor of the given array and store it in variable Y.

Step 3: Take to xor of X and Y to find the duplicate_element.

### Complexity Analysis for finding the duplicate element

Space Complexity: O(1), we are not using any extra memory from the input array.

Time Complexity: O(n), we need to traverse the array just for once. Here n is the size of given array.

### C++ Program

```#include<bits/stdc++.h>
using namespace std;

int findDuplicate(int a[],int n){
int X=0,Y=0;
for(int i=1;i<=n;i++){
X = X^i;
}
for(int i=0;i<=n;i++){
Y = Y^a[i];
}
return X^Y;
}

int main(){
int n;
cin>>n;
int a[n+1];
for(int i=0;i<n+1;i++){
cin>>a[i];
}
int ans = findDuplicate(a,n);
cout<<"Duplicate element is: "<<ans;
}
```
```7
4 5 1 2 4 3 6 7
```
`Duplicate element is: 4`

### JAVA Program

```import java.util.Scanner;

class Main{
static int findDuplicate(int a[],int n){
int X=0,Y=0;
for(int i=1;i<=n;i++){
X = X^i;
}
for(int i=0;i<=n;i++){
Y = Y^a[i];
}
return X^Y;
}

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n;
n = sc.nextInt();
int a[] = new int[n+1];
for(int i=0;i<n+1;i++){
a[i] = sc.nextInt();
}
System.out.println("Duplicate element is: "+findDuplicate(a,n));
}
}
```
```6
3 4 2 1 6 6 5
```
`Duplicate element is: 6`

References

Translate »