| Find unpaired numbers fast and without allocating memory |
Complexity (1-100): 45
A potentially large array of N integers is given. - It
is known that all but one array elements have paired elements
(therefore the array size is odd). Find the value of that unpaired
element.
- It is known that all but two array elements have paired elements
(therefore the array size is even). Find the value of those unpaired
two elements.
You are allowed to spend o(N) time and allocate o(1) amount of memory. |
| Solution: | Show/hide explanation | |
| Explanation |
- XOR all elements. All paired elements will XOR up to zero (as a XOR a = 0). The result of XOR will be the unpaired element.
- XOR all elements. The result will be a XOR b, where a and b are unpaired elements. Because a ≠ b, a XOR b will never be zero. Find a position of any non-zero bit in a XOR b. This is the position in which a and b differ. Then perform second pass and XOR all elements having 1 at this position and all elements having 0 at the same position.
|