/ 
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_i と x のビット単位 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 である。
制約
- 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 は 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
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.
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