โจทย์
ได้รับอาร์เรย์ขนาด n สร้าง sequence ขนาด n×n โดยแต่ละองค์ประกอบคือผลรวมของคู่ (pair) ของทุกองค์ประกอบในอาร์เรย์กับตัวเอง แล้วหา XOR ของ sequence นี้ทั้งหมด
ตัวอย่าง
Input: A = {1, 4, 5}
Output: 0
คำอธิบาย
B = {1+1, 1+4, 1+5, 4+1, 4+4, 4+5, 5+1, 5+4, 5+5}
B = {2, 5, 6, 5, 8, 9, 6, 9, 10}
XOR = 2 ^ 5 ^ 6 ^ 5 ^ 8 ^ 9 ^ 6 ^ 9 ^ 10 = 0
ข้อสังเกตสำคัญ (Key Insight)
ในอาร์เรย์ B ที่สร้างขึ้น:
- คู่
a[i] + a[j]และa[j] + a[i]มีค่าเท่ากัน (commutative) - คู่เหล่านี้จะปรากฏเป็นคู่ (2 ครั้ง) ยกเว้นเมื่อ i = j
- XOR ของค่าเดียวกัน 2 ครั้ง = 0 (cancel out)
- เหลือเฉพาะคู่ที่ i = j คือ
2 * a[i](หรือa[i] + a[i])
ดังนั้น ผลลัพธ์ = XOR ของ 2 * a[i] สำหรับทุก i
= 2 * (a[0] ^ a[1] ^ ... ^ a[n-1])
โค้ดตัวอย่าง
#include <iostream>
using namespace std;
int findSumXor(int arr[], int n) {
int XOR = 0;
for (int i = 0; i < n; i++) {
XOR ^= arr[i];
}
return XOR * 2;
}
int main() {
int arr[3] = {2, 4, 7};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "The xor of the sum pair of elements of the array is: " << findSumXor(arr, n);
return 0;
}
ผลลัพธ์
The xor of the sum pair of elements of the array is: 2
ตรวจสอบ: 2 ^ 4 ^ 7 = 1, 1 * 2 = 2 ✓
การพิสูจน์ทางคณิตศาสตร์
ให้ S = a[0] ^ a[1] ^ ... ^ a[n-1]
ผลรวมทั้งหมดใน B = Σi,j (a[i] + a[j])
แยกเป็น: Σi≠j (a[i] + a[j]) + Σi (2*a[i])
สำหรับ i≠j: (a[i]+a[j]) และ (a[j]+a[i]) เป็นคู่ที่เท่ากัน XOR กัน = 0
เหลือ: Σi (2*a[i]) = 2 * Σi a[i] (ในความหมายของ XOR)
แต่ XOR ไม่ distribute over addition แบบปกติ... อย่างไรก็ตาม 2*x = x << 1 (left shift 1 bit)
และ XOR กับ left shift: (a ^ b) << 1 = (a<<1) ^ (b<<1) เพราะ XOR เป็น bitwise operation
ดังนั้น 2 * (a[0] ^ a[1] ^ ...) = (2*a[0]) ^ (2*a[1]) ^ ... ✓
Complexity
- Time: O(N) - วนลูปเพียงครั้งเดียว
- Space: O(1) - ใช้ตัวแปรคงที่
สรุป
โจทย์ที่ดูเหมือนต้องใช้ O(N2) สามารถลดเป็น O(N) ได้ด้วยการสังเกตคุณสมบัติของ XOR และคู่ที่ซ้ำกัน เป็นตัวอย่างคลาสสิกของการ "คิดก่อนเขียนโค้ด" ใน competitive programming
