ปัญหา
กำหนดอาร์เรย์ arr1, arr2 ต้องการ XOR Sum ของลิสต์ที่ประกอบด้วย arr1[i] AND arr2[j] สำหรับทุกคู่ (i, j) XOR Sum = XOR ของทุกค่าในลิสต์
ตัวอย่าง
arr1 = [5,3,4], arr2 = [2,6]
Pairs: [5&2, 5&6, 3&2, 3&6, 4&2, 4&6] = [0,4,2,2,0,4]
XOR Sum = 0⊕4⊕2⊕2⊕0⊕4 = 0
ข้อสังเกตสำคัญ (Bitwise Property)
XOR Sum ของ (a_i AND b_j) ทุกคู่ = (XOR ของ arr1 ทั้งหมด) AND (XOR ของ arr2 ทั้งหมด)
พิสูจน์: พิจารณาแต่ละบิตแยกกัน บิต k จะเป็น 1 ในผลลัพธ์ก็ต่อเมื่อมีคู่ (i,j) คี่คู่ที่ทั้ง a_i และ b_j มีบิต k = 1 ซึ่งเทียบเท่ากับ (XOR arr1 มีบิต k=1) AND (XOR arr2 มีบิต k=1)
ตัวอย่างโค้ด
def solve(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]
arr2 = [2,6]
print(solve(arr1, arr2)) # 0ความซับซ้อน
- Time: O(n + m)
- Space: O(1)
ดีกว่าวิธี Brute Force O(n×m) มาก
