Score : $500$ points

问题描述

给定一个非负整数序列 $A=(a_1,\ldots,a_N)$。

现在，对序列 $A$ 执行以下操作仅一次：

• 选择一个非负整数 $x$。然后，对于所有 $i=1, \ldots, N$，将 $a_i$ 的值替换为 $a_i$ 和 $x$ 的按位异或结果。

令 $M$ 表示操作后 $A$ 中的最大值。找出 $M$ 可能达到的最小值。

什么是按位异或？非负整数 $A$ 和 $B$ 的按位异或（bitwise XOR）运算记作 $A \oplus B$，定义如下：

• 当 $A \oplus B$ 以二进制表示时，第 $k$ 低位（$k \geq 0$）是 $1$，当且仅当 $A$ 和 $B$ 的第 $k$ 低位中恰好有一个是 $1$，否则该位为 $0$。

例如：$3 \oplus 5 = 6$ （以二进制表示：$011 \oplus 101 = 110$）。

以上为通义千问 qwen-max 翻译，仅供参考。

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.

For instance, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$).

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

update @ 2024/3/10 11:48:48