Vika and Wiki (Codeforces 1848F)
Tags: Math, divide and conquer

Recently, Vika was studying her favorite internet resource - Wikipedia.On the expanses of Wikipedia, she read about an interesting mathematical operation bitwise XOR, denoted by $$$\oplus$$$. Vika began to study the properties of this mysterious operation. To do this, she took an array $$$a$$$ consisting of $$$n$$$ non-negative integers and applied the following operation to all its elements at the same time: $$$a_i = a_i \oplus a_{(i+1) \bmod n}$$$. Here $$$x \bmod y$$$ denotes the remainder of dividing $$$x$$$ by $$$y$$$. The elements of the array are numbered starting from $$$0$$$.Since it is not enough to perform the above actions once for a complete study, Vika repeats them until the array $$$a$$$ becomes all zeros.Determine how many of the above actions it will take to make all elements of the array $$$a$$$ zero. If this moment never comes, output $$$-1$$$.

Input: The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2^{20}$$$) - the length of the array $$$a$$$.It is guaranteed that $$$n$$$ can be represented as $$$2^k$$$ for some integer $$$k$$$ ($$$0 \le k \le 20$$$).The second line contains $$$n$$$ integers $$$a_0, a_1, a_2, \dots, a_{n-1}$$$ ($$$0 \le a_i \le 10^9$$$) - the elements of the array $$$a$$$.

Output: Output a single number - the minimum number of actions required to make all elements of the array $$$a$$$ zero, or $$$-1$$$ if the array $$$a$$$ will never become zero.

Note: In the first example, after one operation, the array $$$a$$$ will become equal to $$$[3, 3, 3, 3]$$$. After one more operation, it will become equal to $$$[0, 0, 0, 0]$$$.In the second example, the array $$$a$$$ initially consists only of zeros.In the third example, after one operation, the array $$$a$$$ will become equal to $$$[0]$$$.

Sample Inputs:
4
1 2 1 2

2
0 0

1
14

8
0 1 2 3 4 5 6 7

Sample Outputs:
2

0

1

5

Solution (Python):
n = int(input())
nums = list(map(int, input().split()))
ans = 0
for i in range(n.bit_length() - 2, -1, -1):
    for idx in range(1 << i):
        if nums[idx] != nums[idx | 1 << i]:
            ans |= 1 << i
            for idx in range(1 << i):
                nums[idx] ^= nums[idx | 1 << i]
            break
if nums[0] != 0:
    ans += 1
print(ans)

Solution (Python):
n = int(input())
arr = list(map(int, input().split()))

def recur(l, r):
    if l == r:
        return 0
    if l + 1 == r:
        return 0 if arr[l] == 0 else 1
    ll = r - l
    stat = True
    for i in range(l, l + ll // 2):
        arr[i] ^= arr[i + ll // 2]
        if arr[i] != 0:
            stat = False
    if stat:
        return recur(l + ll // 2, r)
    else:
        return ll // 2 + recur(l, l + ll // 2)
ans = recur(0, n)
print(ans)
''

Solution (Python):
t = int(input())
s = input()
a = list(map(int, list(s.split())))

def rec(m, b):
    if m == 1:
        if b[0] == 0:
            return 0
        else:
            return 1
    else:
        b_aux = []
        l = m // 2
        b_half = b[:l]
        zero = [0] * l
        for i in range(l):
            b_aux.append(b[i] ^ b[i + l])
        if b_aux == zero:
            return rec(l, b_half)
        else:
            return l + rec(l, b_aux)
print(rec(t, a))