D - Two Xor Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

長さ N の非負整数列 A=(A_1,A_2,\cdots,A_N) が与えられます．

あなたは，次の操作を高々 2 回行うことができます． なお，\oplus はビット単位 \mathrm{XOR} 演算を表します．

  • 非負整数 X を自由に選ぶ． その後，各 i=1,2,\cdots,N について，A_i の値を据え置くかもしくは A_i \oplus X で置き換える．

操作後の A の要素の最大値としてあり得る最小値を求めてください．

ビット単位 \mathrm{XOR} 演算とは

非負整数 A, B のビット単位 \mathrm{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)。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k) と定義され、これは p_1, p_2, p_3, \dots, p_k の順番によらないことが証明できます。

制約

  • 1 \leq N \leq 2^{18}
  • 0 \leq A_i < 2^{18}
  • 入力される値はすべて整数．

入力

入力は以下の形式で標準入力から与えられる．

N
A_1 A_2 \cdots A_N

出力

答えを出力せよ．

入力例 1

4
0 1 2 3

出力例 1

0

例えば，以下のような操作が考えられます．

  • X=1 を選ぶ．
    • i=2 について，A_2 の値を 1 \oplus 1=0 で置き換える．
    • i=4 について，A_4 の値を 3 \oplus 1=2 で置き換える．
  • X=2 を選ぶ．
    • i=3 について，A_3 の値を 2 \oplus 2=0 で置き換える．
    • i=4 について，A_4 の値を 2 \oplus 2=0 で置き換える．

このとき，操作後の A の要素の最大値は 0 になります． これは明らかに達成可能な最小値なので，答えは 0 です．

入力例 2

3
1 4 10

出力例 2

1

入力例 3

5
2023 2023 2023 2023 2023

出力例 3

0

入力例 4

27
206264 140501 79 66028 206233 140291 206082 140347 65912 140301 65824 140404 65851 65986 140497 140526 206162 140513 66031 206294 206085 186 206157 66019 140407 65923 65806

出力例 4

192