Make Them Similar
Contest: Educational Codeforces Round 76 (Rated for Div. 2)
Difficulty rating: 2400
Tags: bitmasks, brute force, hashing, meet-in-the-middle

Let's call two numbers similar if their binary representations contain the same number of digits equal to $$$1$$$. For example:

- $$$2$$$ and $$$4$$$ are similar (binary representations are $$$10$$$ and $$$100$$$);
- $$$1337$$$ and $$$4213$$$ are similar (binary representations are $$$10100111001$$$ and $$$1000001110101$$$);
- $$$3$$$ and $$$2$$$ are not similar (binary representations are $$$11$$$ and $$$10$$$);
- $$$42$$$ and $$$13$$$ are similar (binary representations are $$$101010$$$ and $$$1101$$$).

You are given an array of $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$. You may choose a non-negative integer $$$x$$$, and then get another array of $$$n$$$ integers $$$b_1$$$, $$$b_2$$$, ..., $$$b_n$$$, where $$$b_i = a_i \oplus x$$$ ($$$\oplus$$$ denotes bitwise XOR).

Is it possible to obtain an array $$$b$$$ where all numbers are similar to each other?

Input format:
The first line contains one integer $$$n$$$ ($$$2 \le n \le 100$$$).

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_i \le 2^{30} - 1$$$).

Output format:
If it is impossible to choose $$$x$$$ so that all elements in the resulting array are similar to each other, print one integer $$$-1$$$.

Otherwise, print any non-negative integer not exceeding $$$2^{30} - 1$$$ that can be used as $$$x$$$ so that all elements in the resulting array are similar.

Constraints:
Time limit: 4.0 s
Memory limit: 1024.0 MB

Example input:
2
7 2

Example output:
1

Example input:
4
3 17 6 0

Example output:
5

Editorial:
Iterating over all possible values of $$$x$$$ and checking them may be too slow (though heavily optimized brute force is difficult to eliminate in this problem), so we need to speed this approach up.
The resulting number consists of $$$30$$$ bits. Let's use the classical meet-in-the-middle trick: try all $$$2^{15}$$$ combinations of $$$15$$$ lowest bits, try all $$$2^{15}$$$ combinations of $$$15$$$ highest bits, and somehow "merge" the results.
When we fix a combination of $$$15$$$ lowest bits, we fix $$$15$$$ lowest bits in every $$$b_i$$$. Suppose that there are $$$cnt_{0, i}$$$ ones among $$$15$$$ lowest bits of $$$b_i$$$.
Analogically, when we fix a combination of $$$15$$$ highest bits, we fix $$$15$$$ highest bits in every $$$b_i$$$. Suppose that there are $$$cnt_{1, i}$$$ ones among $$$15$$$ highest bits of $$$b_i$$$.
We want to find a combination of lowest and highest bits such that $$$cnt_{0, i} + cnt_{1, i}$$$ is the same for each $$$i$$$. Let's represent each combination of $$$15$$$ lowest bits with an $$$(n-1)$$$-dimensional vector with coordinates $$$(cnt_{0, 1} - cnt_{0, 2}, cnt_{0, 1} - cnt_{0, 3}, \dots, cnt_{0, 1} - cnt_{0, n})$$$. Let's also represent each combination of $$$15$$$ highest bits with an $$$(n-1)$$$-dimensional vector with coordinates $$$(cnt_{1, 1} - cnt_{1, 2}, cnt_{1, 1} - cnt_{1, 3}, \dots, cnt_{1, 1} - cnt_{1, n})$$$. We want to find a combination of lowest bits and a combination of highest bits such that their vectors are opposite. We can do so, for example, by precalculating all vectors for all combinations of $$$15$$$ lowest bits, storing them in a map or a trie, iterating on a combination of $$$15$$$ highest bits and searching for the opposite vector in the map/trie.