[Solution] Maximum AND solution codeforces

Table of Contents

Maximum AND solution codeforces

Maximum AND solution codeforces – You are given two arrays 𝑎a and 𝑏b, consisting of 𝑛n integers each.

Let’s define a function 𝑓(𝑎,𝑏)f(a,b) as follows:

  • let’s define an array 𝑐c of size 𝑛n, where 𝑐𝑖=𝑎𝑖𝑏𝑖ci=ai⊕bi ( denotes bitwise XOR);
  • the value of the function is 𝑐1&𝑐2&&𝑐𝑛c1&c2&⋯&cn (i.e. bitwise AND of the entire array 𝑐c).

Find the maximum value of the function 𝑓(𝑎,𝑏)f(a,b) if you can reorder the array 𝑏b in an arbitrary way (leaving the initial order is also an option).

Maximum AND solution codeforces

The first line contains one integer 𝑡t (1𝑡1041≤t≤104) — the number of test cases.

The first line of each test case contains one integer 𝑛n (1𝑛1051≤n≤105) — the size of arrays 𝑎a and 𝑏b.

The second line contains 𝑛n integers 𝑎1,𝑎2,,𝑎𝑛a1,a2,…,an (0𝑎𝑖<2300≤ai<230).

The third line contains 𝑛n integers 𝑏1,𝑏2,,𝑏𝑛b1,b2,…,bn (0𝑏𝑖<2300≤bi<230).

The sum of 𝑛n over all test cases does not exceed 105105.

Maximum AND solution codeforces

For each test case print one integer — the maximum value of the function 𝑓(𝑎,𝑏)f(a,b) if you can reorder the array 𝑏b in an arbitrary way.

Example
input

Copy
3
5
1 0 0 3 3
2 3 2 1 0
3
1 1 1
0 0 3
8
0 1 2 3 4 5 6 7
7 6 5 4 3 2 1 0
output

Copy
2
0
7

 

For Solution

“Click Here”

Leave a Comment