Find the two numbers with odd occurrences in an unsorted array

March 25, 2015

Study the algorithm, and work on one algorithm every day.

Here is the website with the question.

http://www.geeksforgeeks.org/find-the-two-numbers-with-odd-occurences-in-an-unsorted-array/

One thing is about bit operation, any number a, a XOR a = 0.

Study the question a few times; sometimes, you just cannot remember the trick.

How about going through an example, for example, an unsorted array, only two numbers with odd occurrences, one is 2, one is 8, how to find those two numbers?

So, 2 is 0010 in binary format, and 8 is 1000 in binary format; since two numbers are different, at least one bit is different; second to rightmost bit is different between 2 and 8. one is 1, and another one is 0. The sum of  XOR operation for those numbers if second to rightmost bit is 0 will be the one of numbers, and then, second number will be the sum of XOR operation for those numbers if second to rightmost bit is 1.