XOR на смежных подмассивах массива

Question

Из массива мне нужно найти значение, полученное посредством XOR-ing непрерывных подмассивов, следуя за XOR-ing полученных таким образом значений.

ВХОД

Одна строка, содержащая целые числа, которые являются элементами массива.

например. [1,2,3]

ВЫВОД

печати ответ, соответствующий каждого теста в отдельной строке.

До сих пор мне удалось создать две стратегии, используя циклы и рекурсивный подход. Ни один из моих подходов не дает хорошей производительности при большом размере ввода.

например. 1 XOR 2 XOR 3 XOR (1 XOR 2) XOR (2 XOR 3) XOR (1 XOR 2 XOR 3) = 2

Не могли бы вы построить лучший алгоритм? Может быть, подход с динамическим программированием?

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

Нам не нужно перечислять (2 ** N) подмассива для решения этого.

У XOR есть некоторые полезные свойства, которые мы можем использовать для решения этой проблемы в O (n) времени. В частности:

• для любых k: k XOR k == 0;
• для любых k: k XOR 0 == k.
• XOR is both commutative and associative.

Чтобы решить вашу проблему, сначала нужно подсчитать, сколько раз каждый элемент появляется в подмассивах. Любой элемент, который появляется четное число раз, можно игнорировать. Остальные должны быть XORed вместе (каждый принимается только один раз).

Давайте посмотрим, как это относится к вашему примеру:

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 

Следующая является реализация О (п) этой идеи:

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]) 

Подсчет подмассивов осуществляется

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

с использованием наблюдения, что есть i + 1 элементы слева от c (включая сам) и n - i справа (также включая сам). Умножение двух дает количество подмассивов, начинающихся слева от текущего элемента и заканчивающихся справа от него.

Теперь мы решили проблему поиска пар (i + 1) и (n - i), чей продукт является нечетным. Обратите внимание, что единственный способ получить нечетный продукт - это умножение двух чисел, которые сами по себе нечетные (это можно увидеть, если подумать о простых факторизациях двух мультипликаций).

Есть два случая:

• когда n даже, один из (i + 1) и (n - i) всегда четно. Это означает, что алгоритм всегда возвращает ноль для списков четной длины.
• , когда n является нечетным, (i + 1) * (n - i) является нечетным для i = 0, 2, 4, ..., (n - 1).

Это приводит к следующему упрощенному раствору:

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