Remove one element to maximize XOR of array

You are given an array of N integer elements,  let's call it arr.

Your task is to remove 1 element from the array in a way the total XOR value of array is maximized, then print the maximized XOR value of array.

On the first line of input you are given N, total number of elements in array. Then following line will contain N space sperated integers, the elements of array.

Example

Input

3
1 1 3

Output

2

Explanation

All possible deletion and corresponding XOR will look like this:

• Let's remove any of the 1, then  (1 XOR 3) = 2
• Remove 3, then 1 XOR 1) = 0

So, here we see, maximum we can get is 2, so 2 would be the answer output we give.

Solution

Naive approach would be to do it the brute force way. i.e. remove each element one by one and compute the XOR in every case and output the maximum one. But the this is very poor apporach and in most of contests, you'll get timeout error. It's time complexity would be O(N²).

Efficient approach would be this:

• Find the total XOR of entire array and store it in a variable, let's call it, M
• Then, For each element arr[i], perform X = (M XOR arr[i]) and update the final answer as ans = max(X, ans).

Why it works ?

It is simple, it works because if (A XOR B) = C then (C XOR B) = A. Now, to find XOR(arr[0…i-1]) ^ XOR(arr[i+1…N-1]), all we have to perform is XOR(arr) ^ arr[i] where XOR(arr) is the XOR of all the elements of the array.

Implementation

// C++ implementation

#include <bits/stdc++.h> 
using namespace std; 

int maxXOR(int* arr, int n) 
{ 
	// Find XOR of the complete array 
	int xorArr = 0; 
	for (int i = 0; i < n; i++) 
		xorArr ^= arr[i]; 

	// To store the final answer 
	int ans = 0; 

	// Iterating through the array to find 
	// the final answer 
	for (int i = 0; i < n; i++) 
		ans = max(ans, (xorArr ^ arr[i])); 

	// Return the final answer 
	return ans; 
} 

// Main function
int main() 
{ 
	int n, arr[100]; // keeping it
	
	for(int i=0; i<n; i++)
	{
		cin>>arr[i];
	}

	cout << maxXOR(arr, n); 

	return 0; 
}