二進表記をした時に \(2^{29}\) の位が \(1\) である非負整数は、( \(2^{28},2^{27},\ldots\) の位に関わらず) \(2^{29}\) の位が \(0\) であるような非負整数より大きいです。そのため、\(i=29,28,\ldots,0\) の順に次の問題を考え、なるべく上位の桁が \(0\) になるよう貪欲に決める、という方法が考えられます。

• \(M\) を二進表記した時の \(2^i\) の位を \(0\) にすることは出来るか。

もし \(a_1,\ldots,a_N\) の \(2^i\) の位がすべて \(0\) ならば、\(x\) の \(2^i\) の位を \(0\) とすることで \(M\) の \(2^i\) の位を \(0\) にすることが出来ます。 \(a_1,\ldots,a_N\) の \(2^i\) の位がすべて \(1\) の場合も同様です。一方、 \(a_1,\ldots,a_N\) の \(2^i\) の位に \(0\) と \(1\) が両方現れる場合、\(M\) の \(2^i\) の位を \(0\) にすることは出来ません(つまり、\(M\) の \(2^i\) の位は \(1\) になります)。

ここで、\(a_1,\ldots,a_N\) の \(2^i\) の位に \(0\) と \(1\) が両方現れる場合において、\(2^i\) の位が \(0\) であるものの集合を \(S\) 、\(1\) であるものの集合を \(T\) とします。仮に \(x\) の \(2^i\) の位を \(0\) にした場合、\(a_i \in S\) に対する \(a_i \oplus x\) の \(2^i\) の位は \(0\) になるため、この時点で \(a_i \oplus x\) が操作後の \(A\) における最大値 になる可能性が無くなると言え、以降は \(T\) に含まれる非負整数のみを考慮すればよくなります。\(x\) の \(2^i\) の位を \(1\) にした場合も同様に \(S\) に含まれる非負整数のみを考慮すればよくなります。問題は、\(2^i\) に関する処理をしている時点では \(S\) を残すべきか \(T\) を残すべきか分からないことです。

実は、\(S\) を残す場合と \(T\) を残す場合を両方試して問題ありません。なぜなら、\(i=29,\ldots,0\) の各段階に対し、\(a_1,\ldots,a_N\) それぞれが残るような以前の操作はちょうど \(1\) 通りしかないためです。

実装は下の例のように再帰的に行うのが(恐らく)一般的です。

実装例(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;
}