← 返回题目列表

AtCoder · abc281_f

I. 异或最小化

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

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

让我们执行以下操作 A 一次。

  • 选择一个非负整数 x。那么,对于每一个 i=1, \ldots, N,替换值 a_i 与按位异或 a_i 和 x.

让 M 是最大值 A 操作后。找到最小可能值 M.

什么是按位异或? 非负整数的按位异或 A 和 B, A \oplus B定义如下。
  • 当 选择 A \oplus B 以二进制形式写入, k- 第最低位 (k \geq 0) 是 1 如果恰好是其中之一 k- 第最低位 A 和 B is 1,和 0 否则。
例如, 3 \oplus 5 = 6 (二进制: 011 \oplus 101 = 110).

约束

  • 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 is 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