find non repating elements in duplicate array

Question

i have an array which all his numbers is shows twice execpt for 3 numbers . For one number i know - to do XOR with all numbers. but for 3 i tried to play with the algoritm for one number - but couldnt find. should be in running time O(n) without hashing . hint : its should be with XOR and with change to bitwise and do modolu.

Answer 1

What are you trying to save? running time or space?

If you are space bounded, do the following:

0)Let $count=3$ 1)Fix an index i. Run on the array and try to find the same number.

2)If succeed, $count=-1$

3)If not, continue to the next index.

If you are time bounded, do the following:

0)Create a hashmap. Keys are the numbers and the values are counters.

1)Run on the array and try inserting the numbers to the hashmap.

2)In the end, return the numbers with counter equal to 1.