The problem of paired numbers

    But the task for the weekend! She is not good enough to ask for an interview, because it is too much for insight (please, never ask such questions at interviews), and is too simple for competitions. Just to deliver the very satisfying click in the brain for which we love programming. So:

    Есть большой массив из N 32-битных чисел. Каждое число встречается два раза, а два числа -- по одному. Найти эти два числа за один проход по массиву с константными затратами памяти (то есть не зависящими от размера массива).

    Don’t forget to use the tagfor solutions in the comments!

    trivial solution: start a zero bitmap with 4G bits (constant memory!). if we see a certain number, we do exclusive or with one at its position. in the end, only two bits will be equal to one - these are the numbers that we were looking for. in one pass through an additional array you can find them.
    Don’t troll :) Let’s avoid discrepancies - you have four kilobytes of memory.

    One solution
    As you can easily see, pair numbers hint that the problem is about xor!
    Let the desired numbers be X and Y. If you just make xor all the numbers in the array, it is clear that the result will be X ^ Y, which is good because all the other numbers are reduced, but it is bad because it does not allow them to be calculated. What to do?
    Note that if we knew in advance in which bit the numbers X and Y are different (and such a bit must be), then the task would be solved simply - let's make xor all the numbers for which in bit N we say one. All paired numbers will be reduced, and the result will be X or Y. And if we also have the value X ^ Y, then the second number is easy to calculate.
    Moreover, if we have X ^ Y it also says in which bit X and Y are different - where in xor 1. It
    remains to understand how to do this in one pass.
    Let's pass xor all numbers and 32 batteries during the passage. In the i-th battery, we will accumulate xor of all numbers that have 1 in the i-th bit. In the end, we will use one of the batteries, where the bits are different.

    There are also many solutions in the comments, with and without code, here are some (the list does not claim to be complete):
    Solution from kmu1990
    Solution from Ogra
    Solution from ZyXI
    How would you solve a problem in a startup from Demogor
    Development of a task from deniskreshikhin
    Disclaimer: the post is written based on fairly edited closedcircles.com chat logs , hence the presentation style and the availability of clarifying questions.

    Also popular now: