Friday, July 25, 2014

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.

Here is the Java Implementation.