Here is a classic algorithmic puzzle probably taken from some interview. You are given integer numbers
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
.
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 , finding any position
in its binary representation such that
and then giving as an answer two numbers:
and
.
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 , they calculate two numbers as an answer:
and
.
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 time, isn’t it?