DFS-B - Dr. Evil Underscores

B - Dr. Evil Underscores

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.

　　题目大意：在给出的n个整数中选出一个整数，使得剩下所有数与这个数的得到的最大异或结果最小

 #include<iostream>

 #include<algorithm>

 #include<vector>

 using namespace std;

 vector<int> v;

 const int N = 1e5 + ;

 int n, x, maxn, cnt;

 int DFS(int cnt, vector<int> v){

     if(v.size()== || cnt<)    return ;//数组中没有整数或二进制有负数位自然不用再考虑

     vector<int> v1, v0;//注意这是在函数中定义的局部的不定长数组

     for(int i=; i<v.size(); i++){

         //判断某数的二进制的某一位上，是1即插入v1，是0即插入v0

         if((v[i]>>cnt) & )        v1.push_back(v[i]);

         else                    v0.push_back(v[i]);

     }

     //若所有整数的二进制在这一位上均为同一个数（不管是0还是1）都可以用0或1使得其异或结果均为0，从而达到使异或结果最小的目的

     if(v1.empty())        return DFS(cnt-, v0);

     else if(v0.empty())    return DFS(cnt-, v1);

     //如果所有整数的二进制在这一位上不可避免的既有1有有0，则其异或结果可以使1也可以是0，而结果是取最大的异或结果，即1

     else                return min(DFS(cnt-, v1), DFS(cnt-, v0)) + (<<cnt);

 }

 int main(){

     scanf("%d", &n);

     for(int i=; i<n; i++){

         scanf("%d", &x);

         v.push_back(x);

         if(x > maxn)    maxn = x;

     }

     //找到其中最大的数，并统计出其二进制有几位

     while(maxn){

         maxn >>= ;

         cnt ++;

     }

     printf("%d",DFS(cnt, v));

     return ;

 }

（1）即使题目放在搜索训练中，我也想不到和搜索有什么关系。其实如果用最简单暴力的方法去做，就是无脑遍历呗，必然超时的原始人操作，这里所用的方法，就是函数递归，递归到头，省时省力。

（2）因为题目中的操作是异或，所有需要将所给的整数，进行二进制处理，而思路也注释在了代码中：如果所有的整数的二进制形式，在某一位上均位同一个数，则很轻易地能用另一个数，使这一位上的异或结果均为0；相反的，如果所有整数在这一位上的数字既有1又有0，也就是不管怎么样，异或结果都会碰到1，题目找到是最大异或结果的最小值，所以当碰到这种结果时只能乖乖取1。

（3）DFS的递归。从最大整数的最高位开始，一位一位地向后递归，在每一位上都得到最理想的异或结果，合起来，就是所求的最大异或结果的最小值。

巴特西

DFS-B - Dr. Evil Underscores

最新文章

热门文章