Home > Applied Algorithms, Bit Manipulation, Sorting > Find the only element in an array which does not have a duplicate. (Only occurs once)

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 no-duplicates-for-it number will give you the number itself. Tada! 🙂

Nice, eh?!

Advertisements
  1. No comments yet.
  1. October 12, 2011 at 9:35 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: