You have an array of integers(size N), such that each integer is present an odd number of time, except 3 of them.Find the three numbers ?

general
1

You have an array of integers(size N), such that each integer is present an odd number of time, except 3 of them(which are present even number of times). Find the three numbers.

Only XOR based solution was permitted.
Time Complexity: O(N)
Space Complexity: O(1)

Sample Input:
{1,6,4,1,4,5,8,8,4,6,8,8,9,7,9,5,9}
Sample Output:
1 6 8

2

I would have thought about using a map.

Iterate trough the array once in O(N) time to “prepare” (ie fill) the map.

Then, iterate over the map, outputting the keys of the pairs, whose value is even.

If we assume that the array of size N has only M distinct elements, where M << N, you have complexity O(M+N) which can be reduced to O(N).

This, however, violates the space complexity constraint, and it’d be nice for me to know the XOR based solution too…