F - Xor Minimization Editorial /

Time Limit: 2.5 sec / Memory Limit: 1024 MB

配点 : 500

問題文

非負整数列 A=(a_1,\ldots,a_N) が与えられます。

A に対して次の操作をちょうど 1 回行います。

  • 非負整数 x を選ぶ。そして、i=1,\ldots,N すべてに対し、a_i の値を「a_ix のビット単位 xor」に置き換える。

操作後の A に含まれる値の最大値を M とします。M の最小値を求めてください。

ビット単位 xor とは 非負整数 A, B のビット単位 xor 、A \oplus B は、以下のように定義されます。
  • A \oplus B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 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) となり、最大値 M16 となります。
M16 より小さくすることは出来ないため、この値が答えです。


入力例 2

10
0 0 0 0 0 0 0 0 0 0

出力例 2

0

入力例 3

5
324097321 555675086 304655177 991244276 9980291

出力例 3

805306368

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.
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