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); | |
} | |
} |