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:
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.
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.
Есть большой массив из N 32-битных чисел. Каждое число встречается два раза, а два числа -- по одному. Найти эти два числа за один проход по массиву с константными затратами памяти (то есть не зависящими от размера массива).
Don’t forget to use the tag
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.
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.