February | 2010 | Algorithms and other stuff

February 22, 2010

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?

M	T	W	T	F	S	S
				Mar »
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28

Algorithms and other stuff

Categories

Archive for February, 2010

Classic puzzle revisited

Tags

Calendar

Archives

Blogroll