XOR trên các mảng con tiếp giáp của một mảng

Question

Từ một mảng, tôi cần phải tìm giá trị thu được bằng XOR-ing các mảng con tiếp giáp, sau đó XOR-ing các giá trị do đó thu được.

ĐẦU VÀO

Một dòng chứa số nguyên đó là những yếu tố của mảng.

ví dụ: [1,2,3]

OUTPUT

In câu trả lời tương ứng với mỗi trường hợp thử nghiệm ở một dòng riêng biệt.

Cho đến nay, tôi đã xây dựng hai chiến lược sử dụng vòng lặp và phương pháp đệ quy. Không có cách tiếp cận nào của tôi có hiệu suất tốt với kích thước đầu vào lớn.

ví dụ: 1 XOR 2 XOR 3 XOR (1 XOR 2) XOR (2 XOR 3) XOR (1 XOR 2 XOR 3) = 2

Bạn có thể xây dựng một thuật toán tốt hơn không? Có lẽ một phương pháp lập trình năng động?

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

Chúng tôi không cần liệt kê (2 ** n) bảng con để giải quyết vấn đề này.

XOR có một số thuộc tính hữu ích mà chúng tôi có thể khai thác để giải quyết vấn đề này trong thời gian O (n). Cụ thể:

• cho bất kỳ k: k XOR k == 0;
• cho bất kỳ k: k XOR 0 == k.
• XOR is both commutative and associative.

Để giải quyết vấn đề của bạn, trước tiên chúng tôi cần tính số lần mỗi phần tử xuất hiện trong các bảng con. Bất kỳ yếu tố nào xuất hiện số lần đều có thể bị bỏ qua. Phần còn lại cần phải được XORed với nhau (mỗi lần lấy một lần).

Hãy xem cách này áp dụng đối với ví dụ của bạn:

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 

Sau đây là một O (n) thực hiện ý tưởng này:

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

Xác định số subarrays được thực hiện bằng

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

sử dụng quan sát rằng có i + 1 phần tử ở bên trái của c yếu tố urrent (bao gồm cả chính nó) và n - i ở bên phải (cũng bao gồm cả chính nó). Nhân hai cung cấp cho số lượng subarrays bắt đầu bên trái của phần tử hiện tại, và kết thúc ở bên phải của nó.

Hiện tại, chúng tôi đã giảm sự cố khi tìm kiếm các cặp (i + 1) và (n - i) có sản phẩm lạ. Quan sát rằng cách duy nhất để có được một sản phẩm lẻ là nhân hai số tự lẻ (điều này có thể được nhìn thấy bằng cách suy nghĩ về các thừa số chính của hai phép nhân).

Có hai trường hợp để xem xét:

• khi n là chẵn một trong (i + 1) và (n - i) luôn là số chẵn. Điều này có nghĩa là thuật toán luôn trả về 0 cho các danh sách có độ dài bằng nhau.
• khi n là số lẻ, (i + 1) * (n - i) là số lẻ cho i = 0, 2, 4, ..., (n - 1).

Điều này dẫn đến các giải pháp đơn giản sau đây:

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