题目描述

难度分:$1714$

输入$n(1 \leq n \leq 150000)$和长为$n$的数组$a(0 \leq a[i] \lt 2^{30})$。

选一个非负整数$x$，然后把每个$a[i]$更新成$a[i] \oplus x$。

输出$max(a)$的最小值。

输入样例$1$

3
12 18 11

输出样例$1$

16

输入样例$2$

10
0 0 0 0 0 0 0 0 0 0

输出样例$2$

0

输入样例$3$

5
324097321 555675086 304655177 991244276 9980291

输出样例$3$

805306368

算法

按位贪心

由于异或运算各位是独立的，因此可以直接从高到底逐为考虑，尽可能让所有数的高位变成$0$。

对于某一位$i$，如果所有元素在这一位都是$0$或者$1$，那么一定可以找到一个$x$，让所有元素在这一位都为$0$。如果这一位既有$0$也有$1$，那最大值在这一位就只能是$1$了，当前位对最大值的贡献是$2^i$，如果$x$的这一位决定让所有在该位是$0$的数在这一位是$0$，那么下一位考虑的就是所有在当前位为$1$的数（因为所有在该位为$0$的为异或之后在当前位是$0$了，绝对不可能是最大值）；反之，如果$x$的这一位决定让所有在该位是$1$的数在这一位是$0$，那么下一位考虑的就是所有在当前位为$0$的数。

复杂度分析

时间复杂度

递归了$30$层，所有层的临时数组的元素个数加起来就是原始数组的$n$，因此时间复杂度为$O(30n)$。

空间复杂度

额外空间就是每层递归的临时数组，仍然是$O(n)$级别。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
int n;

int dfs(vector<int>& a, int depth) {
    if(depth < 0) return 0;
    vector<int> zero, one;
    for(int x: a) {
        if(x>>depth&1) {
            one.push_back(x);
        }else {
            zero.push_back(x);
        }
    }
    if(one.empty()) {
        // 没有1，当前位可以变成0
        return dfs(zero, depth - 1);
    }else if(zero.empty()) {
        // 没有0，当前位也可以变成0
        return dfs(one, depth - 1);
    }
    // 有0又有1，不管x这一位取什么，最大值的这一位都是1
    return min(dfs(zero, depth - 1), dfs(one, depth - 1)) + (1<<depth);
}

int main() {
    scanf("%d", &n);
    vector<int> arr(n);
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    printf("%d\n", dfs(arr, 30));
    return 0;
}