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.

Answer 2

"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.

Answer 3

Basically this can be done as an exercise in rebalancing efficiency: you go through your list of numbers, and for each number you already have in your set, you delete it again. That way your comparison set is about half the size of the possible max. Of course, that does not change O(n lg n), and you get an allocation/deallocation on each step which is likely quite more expensive.

So it might be interesting to use a mixed strategy: quicksort is pretty fast, but you basically want to coalesce two entries whenever they are equal, and at least (n-1)/2 entries are equal. Quicksort does not really accommodate the removal of elements while sorting.

So with an array-based approach (to cut down on allocation costs), I'd rather use some heap-based approach. Whenever you chance upon equal elements, you remove one. Heap sort is pretty competitive with quicksort, and being able to prune the tree in advance is going to turn out helpful.

Answer 4

Find the number occurring odd number of times in an array in Java

package yourPackageNameGoesHere;

import java.util.*;

public class FindTheNumberOccurringOddNumberOfTimesInArray {
public static void main(String[] args) {
    int array [] = {20, 40, 50, 50, 20, 30, 30, 50, 20,20};
    findTheNumberOccurringOddNumberOfTimesInArray(array);
}

public static void findTheNumberOccurringOddNumberOfTimesInArray(int arr[]) {
    Map<Integer, Integer> map = new HashMap<>();

    for (int num : arr) {
        if (map.containsKey(num)) {
            map.put(num, map.get(num) + 1);
        } else {
            map.put(num, 1);
        }
    }
    for (int n : map.keySet()) {
        if (map.get(n) % 2 == 1) {
            System.out.println(n + " is occurring " + map.get(n) + " time(s).");
        }
    }
}

}