388535 (Hard Version) (Codeforces 1658D2)
Tags: Math, bitmasks

This is the hard version of the problem. The difference in the constraints between both versions are colored below in red. You can make hacks only if all versions of the problem are solved.Marin and Gojou are playing hide-and-seek with an array.Gojou initially perform the following steps:   First, Gojou chooses $$$2$$$ integers $$$l$$$ and $$$r$$$ such that $$$l \leq r$$$.  Then, Gojou will make an array $$$a$$$ of length $$$r-l+1$$$ which is a permutation of the array $$$[l,l+1,\ldots,r]$$$.  Finally, Gojou chooses a secret integer $$$x$$$ and sets $$$a_i$$$ to $$$a_i \oplus x$$$ for all $$$i$$$ (where $$$\oplus$$$ denotes the bitwise XOR operation). Marin is then given the values of $$$l,r$$$ and the final array $$$a$$$. She needs to find the secret integer $$$x$$$ to win. Can you help her?Note that there may be multiple possible $$$x$$$ that Gojou could have chosen. Marin can find any possible $$$x$$$ that could have resulted in the final value of $$$a$$$.

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases.In the first line of each test case contains two integers $$$l$$$ and $$$r$$$ ($$$\color{red}{\boldsymbol{0} \boldsymbol{\le} \boldsymbol{l}} \le r < 2^{17}$$$).The second line contains $$$r - l + 1$$$ space-seperated integers of $$$a_1,a_2,\ldots,a_{r-l+1}$$$ ($$$0 \le a_i < 2^{17}$$$). It is guaranteed that array $$$a$$$ is valid.It is guaranteed that the sum of $$$r - l + 1$$$ over all test cases does not exceed $$$2^{17}$$$.

Output: For each test case print an integer $$$x$$$. If there are multiple answers, print any.

Note: In the first test case, the original array is $$$[7, 6, 5, 4]$$$. In the second test case, the original array is $$$[4, 7, 6, 5]$$$.In the third test case, the original array is $$$[3, 1, 2]$$$.

Sample Inputs:
3
4 7
3 2 1 0
4 7
4 7 6 5
1 3
0 2 1

Sample Outputs:
4
0
3

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def solve(a, l, r):
    for i in a:
        if i ^ 1 not in a:
            for i_org in [l, r]:
                x = i ^ i_org
                if a == {j_org ^ x for j_org in range(l, r + 1)}:
                    return x
    return solve(set([i >> 1 for i in a]), l >> 1, r >> 1) << 1
for _ in range(int(input())):
    (l, r) = map(int, input().split())
    a = list(map(int, input().split()))
    print(solve(set(a), l, r))

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def solve(a, l, r):
    for i in a:
        if i ^ 1 not in a:
            x = i ^ l
            if a == {j_org ^ x for j_org in range(l, r + 1)}:
                return x
            x = i ^ r
            if a == {j_org ^ x for j_org in range(l, r + 1)}:
                return x
    return solve({i >> 1 for i in a}, l >> 1, r >> 1) << 1
for _ in range(int(input())):
    (l, r) = map(int, input().split())
    a = list(map(int, input().split()))
    print(solve(set(a), l, r))

Solution (Python):
import sys
input_buffered = sys.stdin.buffer.readline

def find_unique_xor_element(elements, left, right):
    for element in elements:
        if element ^ 1 not in elements:
            for element_original in [left, right]:
                xor_value = element ^ element_original
                if elements == {element_original ^ xor_value for element_original in range(left, right + 1)}:
                    return xor_value
    return find_unique_xor_element(set([element >> 1 for element in elements]), left >> 1, right >> 1) << 1
for _ in range(int(input_buffered())):
    (left_value, right_value) = map(int, input_buffered().split())
    array_elements = list(map(int, input_buffered().split()))
    print(find_unique_xor_element(set(array_elements), left_value, right_value))