4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ To what set, $X$ can belong? $\endgroup$ – Mayank Deora Dec 26 '16 at 5:21
  • $\begingroup$ Any decimal number from [0; 10^18] as well. One can notice that X = A[i] ^ B[j] for some i, j so it kinda reduces posibilities $\endgroup$ – i.trofimow Dec 26 '16 at 5:36
  • $\begingroup$ Do the counts of elements in $A$ and $B$ have to match? So if there are five copies of $1$ in $A$ there must be exactly five copies of $1\text^ X$ in $B$? $\endgroup$ – Ross Millikan Dec 26 '16 at 5:37
  • $\begingroup$ A and B should be equal as multisets, so - Yes. $\endgroup$ – i.trofimow Dec 26 '16 at 5:38
  • 1
    $\begingroup$ Note that if A^X=B then A=B^X and A^B=X $\endgroup$ – polfosol Dec 26 '16 at 5:40
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Question is more appropriate for cs.stackexchange. Sorry for late answering $\endgroup$ – Mayank Deora Dec 26 '16 at 12:21
  • 1
    $\begingroup$ Your approach works unless half the elements of $A$ have a $1$ in a given bit and the same for $B$. That is why I said a malicious setter could give you that situation. $\endgroup$ – Ross Millikan Dec 26 '16 at 16:55
  • $\begingroup$ @RossMillikan, Check my modified answer. I think that you are saying about like example A={000,110,101,011} and B={111,001,100,110} $\endgroup$ – Mayank Deora Dec 27 '16 at 2:00
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Well, there are plenty of tricks to report failure, but there might be cases where amount of possible X-s is like LARGE $\endgroup$ – i.trofimow Dec 26 '16 at 6:00
  • $\begingroup$ It could be. A malicious source could give you sets with no duplicate elements and every bit being $1$ exactly half the time. You could use this model to try to prove the worst case time is something like your brute force number. Often the worst case problems have to be carefully constructed to be hard while most examples in the class are easy. $\endgroup$ – Ross Millikan Dec 26 '16 at 6:19
  • $\begingroup$ Yeap, you are right, but my source is defenitely malicious, so there would be such cases you just described $\endgroup$ – i.trofimow Dec 26 '16 at 6:22
  • $\begingroup$ Actually if every bit is 1 exactly half times then A[i] ^ B[j] is ok answer for any i, j. I dunno why but i just checked it $\endgroup$ – i.trofimow Dec 26 '16 at 6:26
  • $\begingroup$ I meant if there is a solution - then any pair is ok $\endgroup$ – i.trofimow Dec 26 '16 at 6:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.