ผลรวม XOR ของผลบวกทุกคู่ในอาร์เรย์ใน C++

บทนำ

โจทย์: หา XOR ของ (arr[i] + arr[j]) สำหรับทุกคู่ (i, j) รวม i=j ด้วย

วิธีที่ 1: Brute Force O(n²)

int findSumXORPair(int arr[], int n) {
    int XorSum = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            XorSum = XorSum ^ (arr[i] + arr[j]);
    return XorSum;
}

วิธีที่ 2: ใช้สมบัติ XOR O(n)

สังเกตว่า (a+b) XOR (b+a) = 0 เพราะ a+b = b+a คู่ที่ i≠j จะมาคู่กัน (i,j) และ (j,i) → XOR กันออก → เหลือแต่คู่ i=j แต่จริงๆ แล้ว: XOR ของทุกคู่ = 2 × (XOR ของทุกสมาชิก) ถ้า n เป็นเลขคี่ หรือ = 0 ถ้า n เป็นเลขคู่ (เพราะแต่ละค่าปรากฏจำนวนคู่ครั้ง)

โค้ดตัวอย่างใช้: XorSum = 2 × (XOR ทุกตัว)

ตัวอย่างโค้ด (วิธี 2)

#include <iostream>
using namespace std;

int findSumXORPair(int arr[], int n) {
    int XorSum = 0;
    for (int i = 0; i < n; i++)
        XorSum = XorSum ^ arr[i];
    XorSum = 2 * XorSum;
    return XorSum;
}

int main() {
    int arr[] = {5, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "XOR of sum of all pairs in an array is " << findSumXORPair(arr, n);
    return 0;
}

ผลลัพธ์

XOR of sum of all pairs in an array is 22

ตรวจสอบ

5^7^9 = 11 (1011₂) → 2×11 = 22 ✓ Brute force: (5+5)^(5+7)^(5+9)^(7+5)^(7+7)^(7+9)^(9+5)^(9+7)^(9+9) = 10^12^14^12^14^16^14^16^18 = 22 ✓

สรุป

ใช้สมบัติ XOR ลดความซับซ้อนจาก O(n²) เป็น O(n) เทคนิคสำคัญใน Bit Manipulation