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?

Like this:

Be the first to like this post.

2 Responses to “Classic puzzle revisited”

Feed for this Entry Trackback Address

1 huh November 25, 2010 at 12:21 pm

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?

- 2 Grigory November 26, 2010 at 12:38 am
  
  Hi,
  
  Using hash tables is forbidden, because
  1) They give expected running time, not worst case.
  2) The children didn’t know about hast tables yet
  
  There is an archive of problems (only in Russian) here: http://dk.school.ioffe.ru/programming/

Algorithms and other stuff