Problem about pair numbers
But the problem for the weekend! It is poorly suited to ask at an interview, because it is too insight (please never ask such at interviews), and too simple to compete. Just to deliver the most satisfying click in the brain for which we love programming. So:
Do not forget to use the <spoiler> tag for solutions in the comments!
A trivial solution: we start a zero bit array with 4 G bits (constant memory!). if we see a certain number, then we do it exclusive or with one in its position. at the end, only two bits will be equal to one — these are the numbers we were looking for. in one pass through the additional array you can find them.
Do not troll :) Let's not have any misunderstandings - 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
Ogra Solution
ZyXI Solution
How to solve a problem in a startup from Demogor
Development task from deniskreshikhin
Disclaimer: The post is written on the basis of fairly edited chat logs closedcircles.com , hence the style of presentation, and the availability of clarifying questions.
N 32- . , -- . ( ).Do not forget to use the <spoiler> tag for solutions in the comments!
A trivial solution: we start a zero bit array with 4 G bits (constant memory!). if we see a certain number, then we do it exclusive or with one in its position. at the end, only two bits will be equal to one — these are the numbers we were looking for. in one pass through the additional array you can find them.
Do not troll :) Let's not have any misunderstandings - you have four kilobytes of memory.
One solution
As you can easily see, the pair numbers hint that the problem is about xor!
Let the required numbers be X and Y. If you just make the xor of 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 badly because it does not allow you to calculate them. What to do?
Note that if we knew in advance in which bit the numbers X and Y are different (and such a bit should be required), then the problem would be solved simply - let's make xor of all the numbers that say one in bit N. All pair 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 bits X and Y differ - where in xor 1.
It remains to understand how to do it in one pass.
During the passage let us count the xor of all numbers and 32 batteries. In the i-th battery, we will accumulate the xor of all the numbers that have 1 in the i-th bit. In the end, we use one of the batteries, where the bits are different.
Let the required numbers be X and Y. If you just make the xor of 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 badly because it does not allow you to calculate them. What to do?
Note that if we knew in advance in which bit the numbers X and Y are different (and such a bit should be required), then the problem would be solved simply - let's make xor of all the numbers that say one in bit N. All pair 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 bits X and Y differ - where in xor 1.
It remains to understand how to do it in one pass.
During the passage let us count the xor of all numbers and 32 batteries. In the i-th battery, we will accumulate the xor of all the numbers that have 1 in the i-th bit. In the end, we 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
Ogra Solution
ZyXI Solution
How to solve a problem in a startup from Demogor
Development task from deniskreshikhin
Disclaimer: The post is written on the basis of fairly edited chat logs closedcircles.com , hence the style of presentation, and the availability of clarifying questions.
')
Source: https://habr.com/ru/post/280192/
All Articles