Home »
Algorithms
Given an array of n numbers, Check whether there is any duplicate or not
In this article, we are going to learn how to check whether there is any duplicate number in a given array or not?
Submitted by Radib Kar, on October 26, 2018
This is a searching problem which can be solved using brute force approach. But here we are going to see use of hash table to solve such searching problems at lower time complexity.
Algorithm:
Hash table is a simple and effective data structure to solve searching problems in O(1) time complexity. Hash tables can be easily built using STL in C++.
The algorithm to solve the problem:
- Create hash table.
- Set element pointer to 0. (starting from array[0], first element)
- Search for the element in the Hash table.
- If found there is duplicate. Print "duplicate found" & return from program.
- Else insert the element to the hash table.
- If end of the array is reached, exit and print "no duplicate found".
- Else increase the element pointer and go to step 3 (continue).
Time complexity: O(1) for searching hash table, O(n) overall
Space complexity: O(n) (for creating hash table)
Creating hash table using STL
Hash table is created using unordered_set in STL.
C++ implementation
#include<bits/stdc++.h>
using namespace std;
void checkDuplicate(unordered_set<int> hash, int* a, int n){
for(int i=0;i<n;i++){
if(hash.find(a[i])==hash.end()){
hash.insert(a[i]);
}
else{
printf("Duplicate found.....\n");
return;
}
}
printf("No duplicates found........\n");
}
int main(){
int n,x,count=0;
printf("how many elements do you want in your array\n");
scanf("%d",&n);
printf("enter elements\n");
// dynamic array created
int* a=(int*)(malloc(sizeof(int)*n));
// creating hash table
unordered_set <int> hash;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
// function to check duplicate exists or not
checkDuplicate(hash,a,n);
return 0;
}
Output
First run:
how many elements do you want in your array
5
enter elements
1 2 3 4 5
No duplicates found........
Second run:
how many elements do you want in your array
6
enter elements
3 2 1 3 5 6
Duplicate found.....