Find the only element in an array which does not have a duplicate. (Only occurs once)
While this question might seem eerily similar to the last one, it is vastly different. Here, you have an array in which every element has a duplicate except one element. For example,
2, 2, 3, 4, 5, 9, 5, 4, 9, 1, 3
Here, 1 is your expected answer since it does not have a duplicate. So how would you go about tackling this question? I will point out three approaches :
1. Sort the array. It will take O(n lg n) time with a sorting method like Quick Sort (or one of the others we discussed previously). Once the array is sorted, you just need to move through the array once and compare every pair of consecutive elements. The first pair that isn’t equal will be your answer. Sorting the earlier example, we get,
1, 2, 2, 3, 3, 4, 4, 5, 5, 9, 9
You can quickly find that 1 occurs only once by this kind of comparison.
2. Counting the number of times a number occurs by utilizing another array. But this can only be used when you have an fixed range within which the elements can be. Even if we have such a range given, this way takes O(n) of both time and space. Can we do better?
3. Yes, we can do better. The best method will take only time O(n) and utilizes bit manipulation. All you need to do is move through the array once and XOR each element. In the previous example, we would do,
2^2^3^4^5^9^5^4^9^1^3 (XOR sign – ^)
The result will be 1, i.e., your answer. Why? XOR has the property of setting bit as zero if the two bits being XORed are same. Also, it follows the commutative property. The above expression is equivalent to,
1^2^2^3^3^4^4^5^5^9^9
Hence, all duplicates will give a zero. And zero XORed with your noduplicatesforit number will give you the number itself. Tada! 🙂
Nice, eh?!

October 12, 2011 at 9:35 pmBit Manipulation (Overview) « All About Algorithms