What is the greedy approach for this?

Question

We have an array of n numbers which all of them except one have been repeated an even amount of times in this array; we want to find the number that is repeated an odd number of times.

I think the optimum algorithm has time complexity better than O( n Log(n) ) because we can sort the array and then iterate it and when ever we see a new number we increase an accumulator and when we see it again we decrease the accumulator and at the end each member whose accumulator is not zero have been repeated odd times.

Also I think it does not have an algorithm better than O(n) because if it has then it must be O( Log(n) ) and for that we need a sorted array but our initial array is not.

Answer 1

If the numbers are integers you can just xor all the values in your array. The result is the number that is repeated odd number of times(it is correct because x xor x = 0 for any x). The complexity of this algorithm is obviously O(n).