Dr. Evil Underscores (Codeforces 1285D)
Tags: Greedy, divide and conquer

Today, as a friendship gift, Bakry gave Badawy $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ and challenged him to choose an integer $$$X$$$ such that the value $$$\underset{1 \leq i \leq n}{\max} (a_i \oplus X)$$$ is minimum possible, where $$$\oplus$$$ denotes the bitwise XOR operation.As always, Badawy is too lazy, so you decided to help him and find the minimum possible value of $$$\underset{1 \leq i \leq n}{\max} (a_i \oplus X)$$$.

Input: The first line contains integer $$$n$$$ ($$$1\le n \le 10^5$$$).The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2^{30}-1$$$).

Output: Print one integer — the minimum possible value of $$$\underset{1 \leq i \leq n}{\max} (a_i \oplus X)$$$.

Note: In the first sample, we can choose $$$X = 3$$$.In the second sample, we can choose $$$X = 5$$$.

Sample Inputs:
3
1 2 3

2
1 5

Sample Outputs:
2

4

Solution (Python):
import bisect
import collections
input()
a = [int(_) for _ in input().strip().split()]
a.sort()
que = collections.deque()

def recur(su, a, cur, exp, lo, hi):
    global que
    if exp == -1:
        return
    newcur = cur + (1 << exp)
    ind = bisect.bisect_left(a, newcur, lo, hi)
    if ind != hi and ind != lo:
        que.append((su + (1 << exp), a, cur, exp - 1, lo, ind))
        que.append((su + (1 << exp), a, newcur, exp - 1, ind, hi))
    if ind == hi:
        que.append((su, a, cur, exp - 1, lo, hi))
    if ind == lo:
        que.append((su, a, newcur, exp - 1, lo, hi))
que.append((0, a, 0, 31, 0, len(a)))
si = len(que)
ma = 0
while si:
    ele = que.pop()
    ma = ele[0]
    que.append(ele)
    for q in que:
        ma = min(ma, q[0])
    while si:
        ele = que.popleft()
        if ele[0] == ma:
            recur(*ele)
        si -= 1
    si = len(que)
print(ma)

Solution (Python):
n = int(input())
a = [int(x) for x in input().split(' ')]
a.sort()
b = pow(2, 30)
while b > 0 and a[n - 1] % b == a[n - 1]:
    b /= 2
b = int(b)
if b == 0:
    print(0)
    exit(0)

def sol(nums, lo, hi, bit):
    bit = int(bit)
    if bit < 1:
        return (nums[lo] % 2, 0)
    if hi - lo == 0:
        return (nums[lo] % (bit * 2), 0)
    ind = lo
    while ind <= hi and nums[ind] & bit != bit:
        ind += 1
    if ind - 1 - lo < 0:
        (x, maxi) = sol(nums, ind, hi, bit / 2)
        return (x + bit, maxi)
    elif hi - ind < 0:
        (x, maxi) = sol(nums, lo, ind - 1, bit / 2)
        return (x, maxi)
    else:
        (x_l, maxi_l) = sol(nums, lo, ind - 1, bit / 2)
        (x_r, maxi_r) = sol(nums, ind, hi, bit / 2)
        if maxi_l <= maxi_r:
            return (x_l + bit, maxi_l + bit)
        else:
            return (x_r, maxi_r + bit)
(X, ans) = sol(a, 0, n - 1, b)
print(ans)

Solution (Python):
def solve(nums, bit):
    if len(nums) == 1:
        return 0
    lo = {x for x in nums if x & bit}
    hi = nums - lo
    if not lo:
        return solve(hi, bit >> 1)
    if not hi:
        return solve(lo, bit >> 1)
    return bit + min(solve(lo, bit >> 1), solve(hi, bit >> 1))
input()
nums = set(map(int, input().split()))
print(solve(nums, 1 << 30))