XOR Construction (Codeforces 1895D)
Tags: Math, string suffix structures

You are given $$$n-1$$$ integers $$$a_1, a_2, \dots, a_{n-1}$$$.Your task is to construct an array $$$b_1, b_2, \dots, b_n$$$ such that:  every integer from $$$0$$$ to $$$n-1$$$ appears in $$$b$$$ exactly once;  for every $$$i$$$ from $$$1$$$ to $$$n-1$$$, $$$b_i \oplus b_{i+1} = a_i$$$ (where $$$\oplus$$$ denotes the bitwise XOR operator). 

Input: The first line contains one integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).The second line contains $$$n-1$$$ integers $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$0 \le a_i \le 2n$$$).Additional constraint on the input: it's always possible to construct at least one valid array $$$b$$$ from the given sequence $$$a$$$.

Output: Print $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$. If there are multiple such arrays, you may print any of them.


Sample Inputs:
4
2 1 2

6
1 6 1 4 1

Sample Outputs:
0 2 3 1

2 3 5 4 0 1

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
x = bin(n)
r = len(x) - x.rfind('1') - 1
a = [*map(int, input().split())]
(A, c, p, t) = ([0] * n, [0], 0, 0)
for i in range(n - 1):
    p ^= a[i] >> r
    c.append(p)
c = list(set(c))
p = 0
for i in range(n >> r):
    t ^= i
    p ^= c[i]
A[0] = (t ^ p) << r
for i in range(n - 1):
    A[i + 1] = A[i] ^ a[i]
print(*A)

Solution (Python):
import sys
from collections import defaultdict
input = sys.stdin.readline

def out(output):
    sys.stdout.write(str(output) + '\n')

def geti(n):
    position = 0
    while n - 1 >> position > 0:
        position += 1
    return position - 1

def computeb1(arr, i, b1):
    if len(arr) == 0:
        return b1
    arr1 = []
    arr0 = []
    mask = 1 << i
    if mask > len(arr):
        if arr[0] & mask == 0:
            return computeb1(arr, i - 1, b1)
        else:
            return computeb1(arr, i - 1, b1 | mask)
    for n in arr:
        result = n & mask
        if result != 0:
            arr1.append(n)
        else:
            arr0.append(n)
    if len(arr1) == mask:
        return computeb1(arr0, i - 1, b1 | mask)
    else:
        return computeb1(arr1, i - 1, b1)

def generate(b1, nums):
    res = []
    res.append(b1)
    for n in nums:
        res.append(b1 ^ n)
    return res
n = int(input())
nums = list(map(int, input().split()))
asums = []
s = 0
for num in nums:
    s = s ^ num
    asums.append(s)
b1 = computeb1(asums, geti(len(asums) + 1), 0)
res = generate(b1, asums)
f = ''
for r in res[:-1]:
    sys.stdout.write(str(r) + ' ')
sys.stdout.write(str(res[-1]))

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
x = bin(n)
r = len(x) - x.rfind('1') - 1
a = [*map(int, input().split())]
(A, c, p, t) = ([0] * n, [0], 0, 0)
for i in range(n - 1):
    p ^= a[i] >> r
    c.append(p)
c = list(set(c))
p = 0
for i in range(n >> r):
    t ^= i
    p ^= c[i]
A[0] = (t ^ p) << r
for i in range(n - 1):
    A[i + 1] = A[i] ^ a[i]
print(*A)