Today, as a friendship gift, Bakry gave Badawy nn integers a1,a2,…,ana1,a2,…,an and challenged him to choose an integer XX such that the value max1≤i≤n(ai⊕X)max1≤i≤n(ai⊕X) is minimum possible, where ⊕⊕ denotes the bitwise XOR operation.

As always, Badawy is too lazy, so you decided to help him and find the minimum possible value of max1≤i≤n(ai⊕X)max1≤i≤n(ai⊕X).

Input
The first line contains integer nn (1≤n≤1051≤n≤105).

The second line contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai≤230?10≤ai≤230?1).

Output
Print one integer — the minimum possible value of max1≤i≤n(ai⊕X)max1≤i≤n(ai⊕X).

Examples
Input
3
1 2 3
Output
2
Input
2
1 5
Output
4
Note
In the first sample, we can choose X=3X=3.

In the second sample, we can choose X=5X=5.

題意：找出一個(gè)數(shù)X使得最小，并求出這個(gè)值。
思路：異或值最大，首先想到的是字典樹，但是根據(jù)這個(gè)思路，如果說這一位異或之后的數(shù)字相同，那么這一位就不產(chǎn)生貢獻(xiàn)。如果說這一位異或之后的數(shù)字不相同，那么就產(chǎn)生貢獻(xiàn)(1<<k)。但是我們要求最大值最小，我們只需要看后面的數(shù)產(chǎn)生的貢獻(xiàn)哪個(gè)比較小就可以了。這樣我們把這一位是1的，和這一位是0的分成兩個(gè)集合，分別遞歸下去，取返回值較小的，再加上(1<<k)就可以了。
代碼如下：

#include<bits/stdc++.h> using namespace std;const int maxx=1e5+100; int n;inline int dfs(int k,vector<int> &p) {if(k<0) return 0;if(p.size()==0) return 0;vector<int> p1,p0;for(int i=0;i<p.size();i++){if((p[i]>>k)&1) p1.push_back(p[i]);else p0.push_back(p[i]);}if(p0.size()==0) return dfs(k-1,p1);if(p1.size()==0) return dfs(k-1,p0);return min(dfs(k-1,p1),dfs(k-1,p0))+(1<<k); } int main() {while(scanf("%d",&n)!=EOF){vector<int> p;int x;for(int i=1;i<=n;i++) {scanf("%d",&x);p.push_back(x);}cout<<dfs(30,p)<<endl;}return 0; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的Dr. Evil Underscores（异或最大值最小）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。