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

ภาพรวมปัญหา

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ที่มี n ตัวเลข งานของเราคือสร้างโปรแกรมเพื่อหาผลรวมของ XOR ของทุกซับอาร์เรย์ของอาร์เรย์

ตัวอย่างเพื่อความเข้าใจ

Input: arr[] = {5, 1, 4}
Output: 19
Explanation:
XOR ของทุกซับอาร์เรย์:
XOR {5} = 5
XOR {1} = 1
XOR {4} = 4
XOR {5,1} = 5^1 = 4
XOR {1, 4} = 1^4 = 5
XOR {5, 1, 4} = 5^1^4 = 0
ผลรวม = 5 + 1 + 4 + 4 + 5 + 0 = 19

วิธีแก้ปัญหา

วิธีง่าย (Brute Force)

ใช้ลูปซ้อนกันเพื่อหาซับอาร์เรย์ทั้งหมด แล้วหา XOR ของแต่ละซับอาร์เรย์และบวกเข้าตัวแปรผลรวม

ข้อเสีย: มีความซับซ้อนของเวลาแบบเอ็กซ์โพเนนเชียล ใช้ไม่ได้กับข้อมูลขนาดใหญ่

วิธีที่มีประสิทธิภาพ (Prefix XOR)

ใช้ Prefix Array ที่เก็บค่า XOR สะสมของอิลิเมนต์จนถึงดัชนี i:

prefixarr[i] = arr[0] ^ arr[1] ^ … ^ arr[i]

สูตรหา XOR จากดัชนี i ถึง j:

XOR(i-j) = prefixarr[j] ^ prefixarr[i-1]  (ถ้า i > 0)
XOR(0-j) = prefixarr[j]                   (ถ้า i = 0)

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

int calcSubArrayXORSum(int arr[], int n) {
    int sum = 0;
    int multiplier = 1;
    for (int i = 0; i < 30; i++) {
        int oddCount = 0;
        bool isOdd = 0;
        for (int j = 0; j < n; j++) {
            if ((arr[j] & (1 << i)) > 0)
                isOdd = (!isOdd);
            if (isOdd)
                oddCount++;
        }
        for (int j = 0; j < n; j++) {
            sum += (multiplier * oddCount);
            if ((arr[j] & (1 << i)) > 0)
                oddCount = (n - j - oddCount);
        }
        multiplier *= 2;
    }
    return sum;
}

int main() {
    int arr[] = { 3, 8, 13 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Sum of XOR of all subarrays is " << calcSubArrayXORSum(arr, n);
    return 0;
}

ผลลัพธ์

Sum of XOR of all subarrays is 46