Search code examples
arraysalgorithmsearchdata-structureshashmap

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

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!

Solution

  • "Better" depends on context. Using the hash map or hash set will be faster and has the advantage of not modifying the original array, but it requires O(N) extra memory. Sorting and counting takes longer and modifies the array, but requires no extra memory.

    Which solution you choose depends on whether you can afford the extra memory.