XOR on adjacent array subarrays

Question

From the array, I need to find the value obtained by XOR-adjacent subarrays, following the XOR-ing of the values ​​thus obtained.

ENTRANCE

One line containing integers that are elements of an array.

eg. [1,2,3]

OUTPUT

Print the answer corresponding to each test case in a separate line.

So far, I have managed to create two strategies using loops and a recursive approach. None of my approaches give good performance with a large input size.

eg. 1 XOR 2 XOR 3 XOR (1 XOR 2) XOR (2 XOR 3) XOR (1 XOR 2 XOR 3) = 2

Could you build a better algorithm? Maybe a dynamic programming approach?

from functools import reduce # Calculate the XOR def XOR(L): return reduce(lambda x, y: x ^ y, L) # Recursive approach def allSubArraysXOR(L,L2=None): if L2==None: L2 = L[:-1] if L==[]: if L2==[]: return 0 return allSubArraysXOR(L2,L2[:-1]) return XOR(L) ^ allSubArraysXOR(L[1:],L2) # Loop - yielding approach def getAllWindows(L): for w in range(1, len(L)+1): for i in range(len(L)-w+1): yield XOR(L[i:i+w]) a = [int(a_temp) for a_temp in input().strip().split(' ')] print(allSubArraysXOR(a)) # print(XOR(getAllWindows(a))) 

Answer 1

We do not need to list (2 ** n) subarrays to solve this problem.

XOR has some useful properties that we can use to solve this problem in O (n) time. In particular:

• for any k : k XOR k == 0 ;
• for any k : k XOR 0 == k .
• XOR is commutative and associative .

To solve your problem, you first need to calculate how many times each element appears in subarrays. Any item that appears an even number of times can be ignored. The rest must be XORed together (each taken only once).

See how this applies to your example:

 1 XOR 2 XOR 3 XOR (1 XOR 2) XOR (2 XOR 3) XOR (1 XOR 2 XOR 3) = # open brackets 1 XOR 2 XOR 3 XOR 1 XOR 2 XOR 2 XOR 3 XOR 1 XOR 2 XOR 3 = # reorder 1 XOR 1 XOR 1 XOR 2 XOR 2 XOR 2 XOR 2 XOR 3 XOR 3 XOR 3 = # group (1 XOR 1 XOR 1) XOR (2 XOR 2 XOR 2 XOR 2) XOR (3 XOR 3 XOR 3) = # remove pairs 1 XOR 0 XOR 3 = 1 XOR 3 = 2 

The following is the O (n) implementation of this idea:

 def xor_em(lst): n = len(lst) ret = 0 for i, el in enumerate(lst): count = (i + 1) * (n - i) if count % 2: ret ^= el return ret print xor_em([1, 2, 3]) 

Subarray counting is done

 count = (i + 1) * (n - i) 

using the observation that there are elements i + 1 left of the current element (including yourself) and n - i to the right (also including yourself). Multiplying two gives the number of subarrays that start to the left of the current element and end to the right of it.

Now we have reduced the problem of finding pairs (i + 1) and (n - i) whose product is odd. Note that the only way to get an odd product is to multiply two numbers, which themselves are odd (this can be seen by thinking about simple factorizations of two animations).

Two cases can be considered:

• when n even, one of (i + 1) and (n - i) always even. This means that the algorithm always returns zero for lists of even length.
• when n is odd, (i + 1) * (n - i) is odd for i = 0, 2, 4, ..., (n - 1) .

This leads to the following simplified solution:

 def xor_em(lst): if len(lst) % 2 == 0: return 0 else: return reduce(operator.xor, lst[::2])