Make Almost Equal With Mod (Codeforces 1909B)
Tags: Math, bitmasks

xi - Solar Storm⠀You are given an array $$$a_1, a_2, \dots, a_n$$$ of distinct positive integers. You have to do the following operation exactly once:  choose a positive integer $$$k$$$;  for each $$$i$$$ from $$$1$$$ to $$$n$$$, replace $$$a_i$$$ with $$$a_i \text{ mod } k^\dagger$$$. Find a value of $$$k$$$ such that $$$1 \leq k \leq 10^{18}$$$ and the array $$$a_1, a_2, \dots, a_n$$$ contains exactly $$$2$$$ distinct values at the end of the operation. It can be shown that, under the constraints of the problem, at least one such $$$k$$$ always exists. If there are multiple solutions, you can print any of them.$$$^\dagger$$$ $$$a \text{ mod } b$$$ denotes the remainder after dividing $$$a$$$ by $$$b$$$. For example:   $$$7 \text{ mod } 3=1$$$ since $$$7 = 3 \cdot 2 + 1$$$  $$$15 \text{ mod } 4=3$$$ since $$$15 = 4 \cdot 3 + 3$$$  $$$21 \text{ mod } 1=0$$$ since $$$21 = 21 \cdot 1 + 0$$$ 

Input: Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 100$$$) — the length of the array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{17}$$$) — the initial state of the array. It is guaranteed that all the $$$a_i$$$ are distinct.Note that there are no constraints on the sum of $$$n$$$ over all test cases.

Output: For each test case, output a single integer: a value of $$$k$$$ ($$$1 \leq k \leq 10^{18}$$$) such that the array $$$a_1, a_2, \dots, a_n$$$ contains exactly $$$2$$$ distinct values at the end of the operation.

Note: In the first test case, you can choose $$$k = 7$$$. The array becomes $$$[8 \text{ mod } 7, 15 \text{ mod } 7, 22 \text{ mod } 7, 30 \text{ mod } 7] = [1, 1, 1, 2]$$$, which contains exactly $$$2$$$ distinct values ($$$\{1, 2\}$$$).In the second test case, you can choose $$$k = 30$$$. The array becomes $$$[0, 0, 8, 0, 8]$$$, which contains exactly $$$2$$$ distinct values ($$$\{0, 8\}$$$). Note that choosing $$$k = 10$$$ would also be a valid solution.In the last test case, you can choose $$$k = 10^{18}$$$. The array becomes $$$[2, 1]$$$, which contains exactly $$$2$$$ distinct values ($$$\{1, 2\}$$$). Note that choosing $$$k = 10^{18} + 1$$$ would not be valid, because $$$1 \leq k \leq 10^{18}$$$ must be true.

Sample Inputs:
5
4
8 15 22 30
5
60 90 98 120 308
6
328 769 541 986 215 734
5
1000 2000 7000 11000 16000
2
2 1

Sample Outputs:
7
30
3
5000
1000000000000000000

Solution (Python):
for s in [*open(0)][2::2]:
    p = q = 0
    for x in map(int, s.split()):
        p |= x
        q |= ~x
    p ^= ~q
    print((p & -p) * 2)

Solution (Python):
for s in [*open(0)][2::2]:
    p = q = 0
    for x in map(int, s.split()):
        p |= x
        q |= ~x
    p ^= ~q
    print((p & -p) * 2)

Solution (Python):
for a in [*open(0)][2::2]:
    n = m = 0
    for p in map(int, a.split()):
        n |= p
        m |= ~p
    n ^= ~m
    print((n & -n) * 2)