Find all the elements in an array which occur odd number of times

Question

I came across following problem:

'Find all the elements in an array which occur odd number of times'.

My thoughts about this are:

1. Use HashMap: Add values in the array as keys in the HashMap. The value corresponding to each key will be number of times that key is encountered.

2. Sort the array using Quick sort in O(N log N) and then traverse through the array to check which elements occur odd number of times.

What do you think, is there any other approach to this? If no, then which of these 2 approaches is better?

Thanks in advance!

Answer 1

You can modify your first approach to use a hash set instead of a hash map.

Create an initially empty hash set. Go through the elements of your array. For each element, check the hash set: if the current array element is not in the set, add it; otherwise, remove it.

When you reach the end of the array, your hash set will contain every object that occurs in your array an odd number of times.

Since accessing elements in a hash set is O(1), this algorithm has O(N) time complexity.