XOR(Exclusive OR) problem

Question

Given 2 multisets A and B, |A| = |B|. The task is to find such X that A ^ X = B, where A ^ X means foreach element of A xor it with X; or say that theres no such X. |A| <= 10^5, elements of A, B are decimal number from [0; 10^18].

For example -

If A = {0, 2} and B = {1, 3} then 1 is the answer: A ^ 1 = {1, 3}.

I mean I am looking for algorithm with asymptotic << O(|A|^3 * Log(|A|)) which is straightforward brute force.

Edit: well its seems that intended solution is some 'smart' brute force. FML

Answer 1

We will exploit property of xor operation which says that:

even $\oplus$ even= even $\tag {1}$
similiarly
odd $\oplus$ odd = even $\tag{2}$
even $\oplus$ odd= odd $\oplus$ even=odd $\tag{3}$. We have two sets A and B according to question containing integers ($\ge0$).
The basic concept is that there are only two kinds of numbers either even or odd which is also the key fact in our solution to the problem. Xor operation is like a function here because we want a single X which can map A to B that is
$$B=f(X)=A\oplus X$$ For all even A's the B's will be same and similarly in the case for odd A's also. So basically if in the set A we have m even numbers then m numbers in B would be either even or odd. Suppose m numbers are odd in B. then it is something like this:- $$A(evens) \oplus odd=B(odds) $$ i.e. m evens of A are mapped to m odds of B, the remainings in A which are odd has to be mapped to evens which is true. if at any point the corresponding match is not found then X doesn't exist. Algorithm:
The algorithm is recursive ,you can convert it into iterative but recursion is more obvious here. Hint:

XXOR(A,B)
(1)map A to B according to the equality mentioned above. initially we will get two sets of equivalent mappings from A to B, let it be $f_1$(A(even) to B(odd)) and so $f_2$(A(odd) to B(even)) i.e. $X=odd+X$. if a division is not possible that generates same X in both $f_1$ and $f_2$, then no X exists then exit.
else if we have reached the m.s.b. of the numbers, return X;
(2) right shift each of the integer in both the sets A and B by one position.
(3) According to the example
XXOR(A(even)>>1 ,B(odd)>>1)
XXOR(A(odd)>>1, B(even)>>1)
Complexity: The worst case will be when we will have 2 classes of divisions.In that case: $$T(|A|,10^{18})=4T\left(\frac{|A|}{2},10^{18}/2\right)+4|A|$$ if $$T\left(\frac{|A|}{k},1\right)$$ is reached then terminate. The complexity of this algorithm is $O(|A|^2\times 10^{18})$ in the worst case.

Answer 2

There are some things you can do that are not guaranteed to help, so if you get $A,B$ from a malicious source they will not work. For each bit position, count the number of $1$s among the elements of $A$ and $B$. If there are the same number of $0$s and $1$s you have not gained. If there are the same number of $1$s in $A$ and $B$, that bit of $X$ must be zero. If there are the same number of $1$s in $A$ as $0$s in $B$, that bit of $X$ must be $1$. You can see that in the units bit of your example, were there are $0\ 1$s in $A$ and $0\ 0$s in $B$. If there are neither the same number of $0$s nor $1$s in $B$ as $1$s in $A$ you can report failure immediately. Otherwise you (hopefully) have a relatively small number of $X$s to try. You can sort the elements of $A$ into classes by how many of each there are. If the classes do not match $B$, for example there are five numbers that come in three copies in $A$, but only four in $B$, you can report failure immediately. Now do the above or brute force on the smallest class. Again, you should get relatively few candidates for $X$ to try on the other classes.