Posted in: trivia

Or Permutation codechef solution


Or Permutation codechef solution

Chef has a sequence AA of NN integers. He picked a non-negative integer XX and obtained another sequence BB of NN integers, defined as Bi=AiXBi=Ai∣X for each 1iN1≤i≤N. Unfortunately, he forgot XX, and the sequence BB got jumbled.

Chef wonders what the value of XX is. He gives you the sequence AA and the jumbled sequence BB. Your task is to find whether there is a non-negative integer XX such that there exists a permutation CC of BB satisfying the condition Ci=AiXCi=Ai∣X for each 1iN1≤i≤N.

If there are multiple such XX, find any of them.

Note: Here || represents the bitwise OR operation.

Input Format

  • The first line of the input contains a single integer, TT, denoting the number of test cases. The description of TT test cases follows.
  • Each test case consists of 33 lines of input.
    • The first line of each test case contains a single integer NN.
    • The second line of each test case contains NN space-separated integers, denoting the sequence AA.
    • Or Permutation codechef solution

    • The third line of each test case contains NN space-separated integers, denoting the sequence BB.

Output Format

  • For each test case, output on a new line a single non-negative integer XX that satisfies the given condition. If there is no such XX, print 1−1 instead.


  • 1T1041≤T≤104
  • 1N21051≤N≤2⋅105
  • 0Ai,Bi1090≤Ai,Bi≤109 for each 1iN1≤i≤N
  • The sum of NN over all test cases doesn’t exceed 21052⋅105

Sample Input 1 

Or Permutation codechef solution

0 1
4 5
4 1 2
4 5 2
9 13 12 8
11 10 14 15

Sample Output 1 

Or Permutation codechef solution



Test case 11: Consider C=[B1,B2]=[4,5]C=[B1,B2]=[4,5]. For X=4X=4, we have C1=4=04C1=4=0∣4 and C2=5=14C2=5=1∣4 as required.

Test case 22: No matter what permutation CC of BB we choose, there is no such XX that satisfies the condition Ci=Ai | XCi=Ai | X for all 1iN1≤i≤N.

Test case 33: Consider C=[B1,B4,B3,B2]=[11,15,14,10]C=[B1,B4,B3,B2]=[11,15,14,10]. For X=2X=2, the condition Ci=Ai | XCi=Ai | X is satisfied for all 1iN1≤i≤N. Note that X=10X=10 is also a possible answer.



Click here

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to Top