AT_abc281_f [ABC281F] Xor Minimization

题目描述

给定一个非负整数序列 $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$ 与 $B$ 的按位异或。具体来说，$A \oplus B$ 的二进制表示中，第 $2^k$ 位（$k \geq 0$）的数值为 $A$ 和 $B$ 的二进制表示中第 $2^k$ 位的数值中恰有一个为 $1$ 时为 $1$，否则为 $0$。

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

输入格式

输入以如下格式从标准输入读入：

$N\ a_1\ \ldots\ a_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3
12 18 11

输出 #1

16

输入输出样例 #2

输入 #2

10
0 0 0 0 0 0 0 0 0 0

输出 #2

0

输入输出样例 #3

输入 #3

5
324097321 555675086 304655177 991244276 9980291

输出 #3

805306368

说明/提示

限制条件

• $1 \leq N \leq 1.5 \times 10^5$
• $0 \leq a_i < 2^{30}$
• 输入均为整数

样例解释 1

如果选择 $x=2$ 进行操作，操作后的数列为 $(12 \oplus 2, 18 \oplus 2, 11 \oplus 2) = (14, 16, 9)$，最大值 $M$ 为 $16$。无法使 $M$ 小于 $16$，因此答案为 $16$。

由 ChatGPT 4.1 翻译