Maximum Xor Sum Codechef Solution

Problem

You are given arrays $A$ and $B$ with $N$ non-negative integers each.

An array $X$ of length $N$ is called good, if:

• All elements of the array $X$ are non-negative;
• �1X1​ $|$ �2X2​ $|$ $\dots$ $|$ ��=��Xi​=Ai​ for all $(1\le i\le N)$;
• ��Xi​ $\&$ �(�+1)X(i+1)​ $\&$ $\dots$ $\&$ ��=��XN​=Bi​ for all $(1\le i\le N)$.

Find the maximum bitwise XOR of all elements over all good arrays $X$.
More formally, find the maximum value of �1⊕�2⊕…��X1​⊕X2​⊕…XN​, over all good arrays $X$.
It is guaranteed that at least one such array $X$ exists.

Note that $|,\&,$ and $\oplus$ denote the bitwise or, and, and xor operations respectively.

Input Format

• The first line of input will contain a single integer $T$, denoting the number of test cases.
• Each test case consists of multiple lines of input.
  • The first line of each test case contains one integer $N$ — the size of the array.
  • The next line contains $N$ space-separated integers describing the elements of the array $A$.
  • The next line contains $N$ space-separated integers describing the elements of the array $B$.

Output Format

For each test case, output on a new line, the maximum bitwise XOR of all elements over all good arrays $X$.

Constraints

Sample 1:

2
3
0 3 3
0 2 2
2
2 3
0 1

1
3

Explanation:

Test case $1$: An optimal good array is $X=[0,3,2]$.

• For $i=1$: �1=�1=0A1​=X1​=0 and �1=�1B1​=X1​ $\&$ �2X2​ $\&$ �3=0X3​=0.
• For $i=2$: �2=�1A2​=X1​ $|$ �2=3X2​=3 and �2=�2B2​=X2​ $\&$ �3=2X3​=2.
• For $i=3$: �3=�1A3​=X1​ $|$ �2X2​ $|$ �3=3X3​=3 and �3=�3=2B3​=X3​=2.

The XOR of all elements of $X$ is $0\oplus 3\oplus 2=1$. It can be proven that this is the maximum XOR value for any $X$.

Test case $2$: An optimal good array is $X=[2,1]$.

• For $i=1$: �1=�1=2A1​=X1​=2 and �1=�1B1​=X1​ $\&$ �2=0X2​=0.
• For $i=2$: �2=�1A2​=X1​ $|$ �2=3X2​=3 and �2=�2=1B2​=X2​=1.

The XOR of all elements of $X$ is $2\oplus 1=3$. It can be proven that this is the maximum XOR value for any $X$.