Tổng XOR của tổng tất cả cặp trong mảng C++

Giới thiệu

Cho mảng arr[] kích thước n. Tính XOR của tổng tất cả các cặp (i,j): ΣᵢΣⱼ (arr[i] + arr[j]) với phép XOR.

Ví dụ

arr = [5, 7, 9]

Các cặp và tổng:
(5,5)=10, (5,7)=12, (5,9)=14
(7,5)=12, (7,7)=14, (7,9)=16
(9,5)=14, (9,7)=16, (9,9)=18

XOR: 10⊕12⊕14⊕12⊕14⊕16⊕14⊕16⊕18 = 22

Phương pháp 1: Brute Force O(n²)

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

Phương pháp 2: Tối ưu O(n) - Quan trọng!

Nhận xét: (a+b) xuất hiện 2 lần cho a≠b, 1 lần cho a=b.

XOR của một số với chính nó = 0. Do đó các cặp (i,j) và (j,i) triệt tiêu nhau!

Chỉ còn lại các cặp (i,i): 2×arr[i]

Kết quả = XOR của tất cả (2 × arr[i]) = 2 × (XOR của tất cả arr[i])

Mã nguồn tối ưu

#include <bits/stdc++.h>
using namespace std;

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

int main() {
    int arr[] = {5, 7, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Brute force: " << bruteForceXOR(arr, n) << endl;
    cout << "Optimized:   " << findXOROfPairSums(arr, n) << endl;
    
    // Test thêm
    int test[] = {1, 2, 3, 4};
    cout << "Test [1,2,3,4]: " << findXOROfPairSums(test, 4) << endl;
    
    return 0;
}

Kết quả chạy chương trình

Brute force: 22
Optimized:   22
Test [1,2,3,4]: 8

Chứng minh toán học

Kết quả = ⊕ᵢⱼ (aᵢ + aⱼ)
        = [⊕ᵢ (aᵢ + aᵢ)] ⊕ [⊕ᵢ≠ⱼ (aᵢ + aⱼ)]
        = [⊕ᵢ (2aᵢ)] ⊕ [⊕ᵢ<ⱼ ((aᵢ+aⱼ) ⊕ (aⱼ+aᵢ))]
        = [⊕ᵢ (2aᵢ)] ⊕ [⊕ᵢ<ⱼ 0]        (vì x⊕x=0)
        = ⊕ᵢ (2aᵢ)
        = 2 × (⊕ᵢ aᵢ)   (vì 2a = a<<1, và XOR phân phối qua shift trái)

Phân tích độ phức tạp

Kết luận

Bài toán minh họa đẳng cấp của tư duy toán học trong lập trình: từ O(n²) giảm xuống O(n) nhờ tính chất XOR (x⊕x=0). Kỹ thuật này áp dụng rộng rãi trong competitive programming.