Find the Duplicate Element

Difficulty Level Medium
Frequently asked in Apple Bloomberg Google Microsoft
Array Binary Search Two PointerViews 3800

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 »