102815: [AtCoder]ABC281 F - Xor Minimization
Description
Score : $500$ points
Problem Statement
You are given a sequence of non-negative integers $A=(a_1,\ldots,a_N)$.
Let us perform the following operation on $A$ just once.
- Choose a non-negative integer $x$. Then, for every $i=1, \ldots, N$, replace the value of $a_i$ with the bitwise XOR of $a_i$ and $x$.
Let $M$ be the maximum value in $A$ after the operation. Find the minimum possible value of $M$.
What is bitwise XOR?
The bitwise XOR of non-negative integers $A$ and $B$, $A \oplus B$, is defined as follows.- When $A \oplus B$ is written in binary, the $k$-th lowest bit ($k \geq 0$) is $1$ if exactly one of the $k$-th lowest bits of $A$ and $B$ is $1$, and $0$ otherwise.
Constraints
- $1 \leq N \leq 1.5 \times 10^5$
- $0 \leq a_i \lt 2^{30}$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $a_1$ $\ldots$ $a_N$
Output
Print the answer.
Sample Input 1
3 12 18 11
Sample Output 1
16
If we do the operation with $x=2$, the sequence becomes $(12 \oplus 2,18 \oplus 2, 11 \oplus 2) = (14,16,9)$, where the maximum value $M$ is $16$.
We cannot make $M$ smaller than $16$, so this value is the answer.
Sample Input 2
10 0 0 0 0 0 0 0 0 0 0
Sample Output 2
0
Sample Input 3
5 324097321 555675086 304655177 991244276 9980291
Sample Output 3
805306368
Input
题意翻译
给定一个长度为 $N$ 的序列 $A$，求 $\min\limits^{\infty}_{i=0} \max\limits^N_{k=1} (A_k \oplus i)$，其中 $\oplus$ 是按位异或操作。Output
分数：500分
问题描述
你得到了一个非负整数序列$A=(a_1,\ldots,a_N)$。
我们仅对$A$执行以下操作一次。
- 选择一个非负整数$x$。然后，对于$ i=1, \ldots, N$，将$a_i$的值替换为$a_i$和$x$的按位异或。
设操作后$A$中的最大值为$M$。找到$M$的最小可能值。
什么是按位异或？
非负整数$A$和$B$的按位异或$A \oplus B$定义如下。- 当$A \oplus B$用二进制表示时，第$k$位（$k \geq 0$）为1，如果$A$和$B$的第$k$位中恰好一个为1，否则为0。
限制条件
- $1 \leq N \leq 1.5 \times 10^5$
- $0 \leq a_i \lt 2^{30}$
- 输入中的所有值都是整数。
输入
输入通过标准输入给出以下格式：
$N$ $a_1$ $\ldots$ $a_N$
输出
打印答案。
样例输入1
3 12 18 11
样例输出1
16
如果我们使用$x=2$执行操作，序列变为$(12 \oplus 2,18 \oplus 2, 11 \oplus 2) = (14,16,9)$，其中最大值$M$为$16$。
我们无法使$M$小于$16$，因此该值为答案。
样例输入2
10 0 0 0 0 0 0 0 0 0 0
样例输出2
0
样例输入3
5 324097321 555675086 304655177 991244276 9980291
样例输出3
805306368