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.
Table of Contents
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