XOR on contiguous subarrays of an array

Question

From an array, I need to find the value obtained by XOR-ing the contiguous subarrays, following by XOR-ing the values thus obtained.

INPUT

One line containing integers that are elements of the array.

e.g. [1,2,3]

OUTPUT

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

So far I managed to build two strategy using loops and a recursive approach. None of my approaches are giving a good performance on large input size.

e.g. 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 don't need to enumerate the (2**n) subarrays to solve this.

XOR has some useful properties that we can exploit to solve this in O(n) time. Specifically:

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

To solve your problem, we first need to count how many times each element appears in the subarrays. Any element that appears an even number of times can be disregarded. The rest need to be XORed together (each taken just once).

Let's 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 an 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])

The counting of subarrays is done by

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

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

We've now reduced the problem to looking for pairs (i + 1) and (n - i) whose product is odd. Observe that the only way to get an odd product is by multiplying two numbers that are themselves odd (this can be seen by thinking about the prime factorizations of the two multiplicands).

There are two cases to consider:

• when n is even, one of (i + 1) and (n - i) is 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])