One solution that i can think of is analogous to the solving a more general problem to find two non-repeating elements in an array having all elements repeated once except two (you have to find those two non-repeating elements).
E.g.., 1, 2, 3, 4, 2, 1, 4, 5. Here 3 and 5 are not repeated.
Lets see how it is simmilar to the problem that you have mentioned.
Consider a series from 1-N with two missing numbers. Also, take series of number from 1-N. Now, if you consider it as one series, you have two each instances of each number except for two numbers which are missing in first series.
Now, consider doing exclusive or operation on number x. with itself and with zero.
- x XOR x = x^x = 0, and
- 0 XOR x = 0^x = x
Using these two properties, if we apply XOR on all the elements of the series, then the numbers haveing two instances with lead to zero (from 1) and doesn't contribute to the result (from 2). Thus, the result of xor operation on the all the numbers will be x^y where x and y are two numbers in the missing series.
But wait, we actaully wanted to find x and y seperately, and not x^y.
We will again use a property of XOR operation to do this. All the bits that are set (i.e.., 1) in x^y are set in one of the non-repeating element that is either x or y.
Now consider the rightmost set bit (i.e.., 1) in x^y. Now we group all the numbers in two groups, one having bit set at the rightmost set bit place of x^y and the others having not bit set at that place. Using this grouping, x and y will get into seperate groups. The other remaining repeated elements will either go one group or other.
Now we do XOR operation in intra-group elements. The XOR operation on the group having x will result in x. Same is the case for group in y. Why is it so?
Because all the other remaining numbers have repeated instances and XORing them would result in zero (from 2) and x being non-repeated will remain as x^0 (this zero is coming from XORing other repeated elements) = x.
Same is the case for elements in other group which upon XORing will give us the other non-repeated element i.e.., y.
