Question :
Given 2 arrays 'A' and 'B' both of size 'N'. Make 'N' pairs ( A[ i ], B[ j ] ) such that :
- First element of pair should be from array 'A' and second element from array 'B'. ( we cannot make pair ( A[1], A[3] ) )
- An element cannot occur in more than one pair. { i.e for every 2 pairs ( A[i], B[j] ) , ( A[k], B[l] ) (i != k and j != l) }
- Let the value of a pair be the XOR of first and second element of the pair, value of all the pairs formed must be equal.
Constraints : 0 <= A[i], B[i] <= 10^9 __________ ( 1 <= i <= N )
( Consider N even as the problem can be solved for odd N in O(N) easily )
How to solve it in less than O(N^2) Time Complexity ?
If not possible return -1
Lets try to find x,for ith bit of x let's calculate ith on and off bits in both arrays, if no. of on bits in a is equal to no.of off bits in b, then we can turn ith bit on,else we turn it off.So after finding x, we can easily find pairs by searching a[i]^x in b. Correct me if its wrong.
Sorry for English.
if ith bit in A is set n/2 times and unset n/2 times and in B also ith bit is set n/2 times and unset n/2 times ,so in this case what do we do ? ( Consider n to be even )
Nice Question !
You fix the element A[0] and then find the set of numbers S = {A[0]^B[i], 1<=i<=N}
I believe you know how it goes from here.
Sorry but how is that going to help in getting near to the solution? I mean even if it would that is for sure the first step anyone would try, but what to do next is I suppose what most of us want to know.
Can u kindly explain further steps in a bit more detail?
Let the value of a pair in a correct solution (if it exists) be k then k is in S.
Since A[0] must be xored with some B[i] to get k, right?
For each element e in S, we calculate the multiset B' = {A[i]^e, 1<=i<=N} and then check if this multiset has the same content as the array B. If B' is the same as B then we found the value k.
If there is no e in S that would produce B'=B output -1.
Hope this is clear enough :)
Isn't it O(N^2), if try for every k ?
Oh less than O(N^2). Now I see it. My bad.
As VoidHead said, we can try to find x, using divide and conquer method. I cannot prove the correctness of the algorithm, but my solution works correctly on random tests.
Yes we can solve it this way but the question remains the same can we solve it in less than O(N^2) ?
As you are making 4 recursive calls every time, Please explain the time complexity of your solution .
Yes, I think I was wrong. This solution works O (N ^ 2).
Auto comment: topic has been updated by mtewathia99 (previous revision, new revision, compare).
.
What's the O(n) solution for odd n?
Xor of each pair will be equal to xor of all numbers in A and B if N is odd.
ah, ofc
How ?
Let A = {x1, x2, x3}, B = {y1, y2, y3}
Suppose we made pairs z1 = {x1, y1}, z2 = {x2, y2}, z3 = {x3, y3}
We know, value of z1 = x1^y1, z2 = x2^y2, z3 = x3^y3
Now z1^z2^z3 = x1^y1^x2^y2^x3^y3
As we know XOR is associative
z1^z2^z3 = x1^x2^x3^y1^y2^y3
From the question we also know z1 = z2 = z3 and we also know that XOR of equal values is zero, so
z1^z2^z3 = z1 = z2 = z3 = x1^x2^x3^y1^y2^y3.