Close

Finding the number of duplicates in a list of numbers

Given a list of numbers, we have to find how many duplicate entries are present in it?

For example consider the list of numbers {5, 1, 9, 5, 2, 1, 6, 4, 5, 8}
It has 3 duplicate numbers.

There are many ways to do this. In this post, I present one of the simplest ways using C++ STL set data structure, and Java HashSet data structure
 
The insert() method of the set returns a pair of type 
pair< set<type>::iterator, bool >
 

The second value in the pair is true if a new element is inserted. It is false if there is already an existing element.

The add() method of HashSet returns true if new element is inserted, and false if no new element is inserted(duplicate)

We can make use of this property to count the number of duplicate elements.

Here is the simple C++ implementation.

#include <iostream>
#include <set>
using namespace std;
int main() {
int n;
cin >> n;
set<int> s;
pair< set<int>::iterator, bool > ret;
int i;
int duplicates = 0;
for( i = 0; i < n ; i++ )
{
int num;
cin >> num;
ret = s.insert(num);
if( !ret.second )
duplicates++;
}
cout << duplicates << endl;
return 0;
}

Here is the Java Implementation.

import java.util.*;
import java.lang.*;
import java.io.*;
class Duplicates
{
public static void main (String[] args)
{
Scanner reader = new Scanner(System.in);
int n = reader.nextInt();
HashSet<Integer> hs = new HashSet<Integer>();
int i;
int duplicates = 0;
for( i = 0 ; i < n; i++ )
{
int num = reader.nextInt();
if( !hs.add(num) )
duplicates++;
}
System.out.println(duplicates);
}
}

Leave a Reply

Your email address will not be published. Required fields are marked *