If the \(2^{29}\)’s place in the binary notation of an integer is \(1\), the integer is greater than any integer whose \(2^{29}\)’s place is \(0\) (regardless of \(2^{28}\)’s place, \(2^{27}\)’s place, and so on). Therefore, we come up with a greedy algorithm where we consider the following problem for each \(i=29,28,\ldots,0\) to make the digit \(0\) as many times as possible:

• can we let the \(2^i\)’s place in the binary notation of \(M\) be \(0\)?

If the \(2^i\)’s place of \(a_1,\ldots\), and \(a_N\) are all \(0\), then we can set the \(2^i\)’s place of \(x\) to \(0\) to make the \(2^i\)’s place of \(M\) be \(0\). Same applies to the case where the \(2^i\)’s place of \(a_1,\ldots\), and \(a_N\) are all \(1\). On the other hand, if both \(0\) and \(1\) occur in the \(2^i\)’s place of \(a_1,\ldots\), and \(a_N\), then we cannot let the \(2^i\)’s place of \(M\) be \(0\) (in other words, the \(2^i\)’s place of \(M\) is always \(1\)).

Here, assume that both \(0\) and \(1\) occur in the \(2^i\)’s place of \(a_1,\ldots\), and \(a_N\), and let \(S\) be the set of those whose the digit is \(0\), and \(T\) be those with \(1\). If we let the \(2^i\)’s place of \(x\) be \(0\), then the \(2^i\)’s place of \(a_i \oplus x\) will be \(0\) for each \(a_i \oplus x\), so it is no longer possible that \(a_i \oplus x\) becomes the maximum value of \(A\) after the operation, and we only have to consider the non-negative integers contained in \(T\). Similarly, if we set the \(2^i\)’s place of \(x\) to \(1\), we only have to consider the non-negative integers contained in \(S\). The problem is, we don’t know whether we should preserve \(S\) or \(T\) at the time we process \(2^i\).

In fact, we may try both preserving \(S\) and preserving \(T\). This is because, for each step \(i=29,\ldots,0\), there are only one aforementioned operation that preserves \(a_1,\ldots,a_N\).

The (probably) most general implementation is the following recursive one.

Sample code (C++)

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

int dfs(int cur,vector<int> a){
	
	if(cur==-1)return 0;
	vector<int> S,T;
	
	for(int i=0;i<a.size();i++){
		if(((a[i]>>cur)&1)==0)S.push_back(a[i]);
		else T.push_back(a[i]);
	}
	
	if(S.size()==0)return dfs(cur-1,T);
	if(T.size()==0)return dfs(cur-1,S);
	return min(dfs(cur-1,S),dfs(cur-1,T)) | (1<<cur);
	
}

int main() {
    
	int N;
	cin>>N;
	
	vector<int> a(N);
	for(int i=0;i<N;i++)cin>>a[i];
	
	cout<<dfs(29,a)<<endl;
	
	return 0;
}