Classic puzzle revisited

Here is a classic algorithmic puzzle probably taken from some interview. You are given N integer numbers a_1, \ldots, a_N such that all of them but two can be grouped into pairs in which elements are equal. The goal is to find two numbers that have no pair in time O(N).

The solution is described below, so you should stop here if you want to solve it yourself.

The well-known solution for this puzzle consists of taking XOR of all the numbers x = \bigoplus_i a_i, finding any position j in its binary representation such that x[j] = 1 and then giving as an answer two numbers: \bigoplus\limits_{a_i [j] = 0} a_i and \bigoplus\limits_{a_i [j] = 1} a_i.

Considering this problem as a good exercise for understanding XOR operation, we decided to give it to children on our elective course in olympiad programming (in Russian). The only team that managed to solve it invented a somewhat different solution. Having calculated x = \bigoplus_i a_i, they calculate two numbers as an answer: \bigoplus\limits_{a_i \oplus x \leq a_i} a_i and \bigoplus\limits_{a_i \oplus x > a_i} a_i.

It took me a few moments to understand why does this work. I was really excited when I did — it is an incredible pleasure working with talented children!

This puzzle is a difficult version of a simpler one, in which there is only one number without a pair. Unfortunately, I don’t see how the ideas described above can be modified to handle three or more numbers that have no pair. I think this is impossible to do in O(N) time, isn’t it?

Advertisements

2 Comments to “Classic puzzle revisited”

  1. One could also make a hash table of all the numbers and then for each of a_i see whether x xor a_i exists among the given numbers. If numbers are stored in a hash table, then each query takes O(1) expected time, giving total time complexity of O(n).

    Where can one find such puzzles? Is there a repository or set of training materials for your elective course?

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: