Python में सभी जोड़ों के बिटवाइज़ AND का XOR योग ज्ञात करें

दो सरणियों arr1 और arr2 के लिए, सभी जोड़ों (i, j) के लिए arr1[i] & arr2[j] (बिटवाइज़ AND) की सूची बनाएं, फिर इस सूची का XOR योग ज्ञात करें।

मुख्य अंतर्दृष्टि: गणितीय सरलीकरण

XOR योग के गुणों का उपयोग करके:

XOR(सभी i,j के लिए (arr1[i] & arr2[j]))
= (XOR सभी i के लिए arr1[i]) & (XOR सभी j के लिए arr2[j])
= xor1 & xor2

यह काम करता है क्योंकि XOR वितरण योग्य है AND पर जब एक ऑपरेंड स्थिर होता है, और प्रत्येक बिट स्वतंत्र रूप से योगदान देता है।

Python कार्यान्वयन

def xor_sum_of_and_pairs(arr1, arr2):
    xor1 = 0
    xor2 = 0
    
    for a in arr1:
        xor1 ^= a
    for a in arr2:
        xor2 ^= a
    
    return xor1 & xor2

# परीक्षण
arr1 = [5, 3, 4]  # 101, 011, 100
arr2 = [2, 6]     # 010, 110

print(xor_sum_of_and_pairs(arr1, arr2))  # 0

# मैन्युअल सत्यापन:
# जोड़े: (5&2)=0, (5&6)=4, (3&2)=2, (3&6)=2, (4&2)=0, (4&6)=4
# सूची: [0, 4, 2, 2, 0, 4]
# XOR: 0^4^2^2^0^4 = (4^4)^(2^2)^(0^0) = 0^0^0 = 0

आउटपुट

0

क्यों काम करता है?

प्रत्येक बिट स्थिति के लिए स्वतंत्र रूप से विचार करें। मान लीजिए बिट k:

• arr1 में बिट k सेट वाले तत्वों की संख्या: c1
• arr2 में बिट k सेट वाले तत्वों की संख्या: c2
• परिणामी सूची में बिट k सेट वाले तत्वों की संख्या: c1 × c2
• XOR में बिट k सेट होगा यदि c1 × c2 विषम है
• c1 × c2 विषम ⟺ c1 विषम AND c2 विषम
• c1 विषम ⟺ arr1 का XOR में बिट k सेट है
• c2 विषम ⟺ arr2 का XOR में बिट k सेट है
• इसलिए परिणाम बिट k = (xor1 का बिट k) AND (xor2 का बिट k)

जटिलता

• समय: O(n + m) - केवल दो पास
• स्थान: O(1)
• भोला दृष्टिकोण O(n×m) से घातीय रूप से तेज़

सामान्यीकरण

यह ट्रिक किसी भी एसोसिएटिव ऑपरेशन के लिए काम करती है जहां XOR वितरित होता है। बिटवाइज़ OR के लिए काम नहीं करता।