Tag Archives: Maximum Xor Sum solution codechef

Maximum Xor Sum solution codechef

Maximum Xor Sum solution codechef – You are given arrays  and  with  non-negative integers each.

Maximum Xor Sum solution codechef

An array  of length  is called good, if:

  • All elements of the array  are non-negative;
  • �1  �2    ��=�� for all (1≤�≤�);
  • �� & �(�+1) &  & ��=�� for all (1≤�≤�).

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

Note that ∣,&, and  denote the bitwise orand, and xor operations respectively.

Input Format

  • The first line of input will contain a single integer , 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  — the size of the array.
    • The next line contains  space-separated integers describing the elements of the array .
    • The next line contains  space-separated integers describing the elements of the array .

Maximum Xor Sum solution codechef

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

Constraints

  • 1≤�≤105
  • 1≤�≤105
  • 0≤��<230
  • 0≤��<230
  • It is guaranteed that at least one such array  exists.
  • Sum of  over all test cases is less than 3⋅105.

Sample 1:

Input

Output

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

Maximum Xor Sum solution codechef

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

  • For �=1�1=�1=0 and �1=�1 & �2 & �3=0.
  • For �=2�2=�1  �2=3 and �2=�2 & �3=2.
  • For �=3�3=�1  �2  �3=3 and �3=�3=2.

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

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

  • For �=1�1=�1=2 and �1=�1 & �2=0.
  • For �=2�2=�1  �2=3 and �2=�2=1.

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