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:

1. Create hash table.
2. Set element pointer to 0. (starting from array[0], first element)
3. Search for the element in the Hash table.
4. If found there is duplicate. Print "duplicate found" & return from program.
5. Else insert the element to the hash table.
6. If end of the array is reached, exit and print "no duplicate found".
7. 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.....