How to find all odd occurring elements in an array in Java

Question

I am trying to find all the elements which occur an odd number of times in an array. I worked out a little bit, but my code is only returning the correct answer if there is only one number which occurs odd number of times. If there are two or more odd occurring numbers than I am not able to process it. What I understand is that if we do bit-wise XOR of elements than we get one odd occurring element. How can I improve it for multiple numbers?

Below is my code:

public class OddOccur {
    public int oddoccurence(int[] arr, int size) {
        int res = 0;
        int[] fin = new int[size];

        for (int i = 0; i < size; i++) {
            res = res ^ arr[i];

        }
        return res;
    }

    public static void main(String args[]) {
        int[] arr = { 2, 5, 5, 2, 2, 3, 3, 3 };

        int n = arr.length;
        OddOccur obj = new OddOccur();

        System.out.println("odd occuring element is:"
                + obj.oddoccurence(arr, n));
    }
}

Need help to solve this issue!

Answer 1

public int oddoccurence(int[] arr, int size);

First, there can be multiple numbers that occur an odd number of times. There's no way to write this function and make it work if it only returns a single int. You'll need a function which can return multiple numbers.

public int[] oddOccurrences(int[] array);

Second, don't try to be clever. Using XOR is "clever". You're not going to find a simple solution using XOR. It'll be some convoluted, complicated mess. Keep it simple:

1. Count the number of times each number appears.
2. Then find all the odd counts.

Example pseudo-code:

// Map from numbers to counts. Assume the counts start at 0.
Map<Integer, Integer> counts;

for (number in array) {
    counts[number] += 1
}

// List of numbers that occur an odd number of items.
List<Integer> oddNumbers;

for (number, count in counts) {
    if (count % 2 != 0) {
        oddNumbers.add(number);
    }
}