异或最小值

题目描述

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

我们对 $A$ 只进行一次如下操作。

选择一个非负整数 $x$。然后对每个 $i=1, \ldots, N$,把 $a_i$ 替换为 $a_i$ 与 $x$ 的按位异或(XOR)。

设 $M$ 为操作后 $A$ 中的最大值。求 $M$ 可能的最小值。

输入格式

输入按以下格式从标准输入给出。

$N$
$a_1$ $\ldots$ $a_N$

输出格式

输出答案。

样例

3
12 18 11

16

若用 $x=2$ 进行操作,序列变为 $(12 \oplus 2,18 \oplus 2, 11 \oplus 2) = (14,16,9)$,此时最大值 $M$ 为 $16$。

我们无法把 $M$ 降到 $16$ 以下,所以这个值就是答案。

10
0 0 0 0 0 0 0 0 0 0

0

5
324097321 555675086 304655177 991244276 9980291

805306368

数据范围

• $1 \le N \le 1.5 \times 10^5$
• $0 \le a_i \lt 2^{30}$
• 输入中的所有值均为整数。

提示

什么是按位异或(XOR)?

非负整数 $A$ 和 $B$ 的按位异或 $A \oplus B$ 定义如下。

当 $A \oplus B$ 用二进制表示时,其从低位起的第 $k$ 位($k \geq 0$)在 $A$ 和 $B$ 的第 $k$ 位中恰好有一位为 $1$ 时为 $1$,否则为 $0$。

例如,$3 \oplus 5 = 6$(二进制表示为 $011 \oplus 101 = 110$)。