XOR của tất cả XOR con mảng trong C++

Trong bài toán này, cho một mảng n phần tử. Nhiệm vụ là in ra XOR của XOR tất cả các con mảng (subarray) có thể tạo ra từ các phần tử của mảng.

Ví dụ:

Input – mảng = {1, 3, 6, 8}

Output – 0

Giải thích –

(1) ^ (3) ^ (6) ^ (8) ^ (1^3) ^ (3^6) ^ (6^8) ^ (1^3^6) ^ (3^6^8) ^ (1^3^6^8)

Cách tiếp cận đơn giản là duyệt tất cả con mảng và tìm XOR, nhưng không hiệu quả. Cách tốt hơn: đếm tần suất xuất hiện của mỗi phần tử trong tất cả con mảng, dùng tính chất XOR – XOR của phần tử chẵn lần là 0. Bỏ qua các giá trị xuất hiện chẵn lần, chỉ XOR các phần tử xuất hiện lẻ lần.

Tần suất xuất hiện của phần tử tại chỉ số i trong tất cả con mảng: (i+1)*(n-i).

Dùng công thức này tìm tần suất, nếu lẻ thì XOR vào kết quả.

Ví dụ minh họa

#include <iostream>
using namespace std;

int xorSubarrayXors(int arr[], int N) {
    int result = 0;
    for (int i = 0; i < N; i++) {
        int frequency = (i + 1) * (N - i);
        if (frequency % 2 == 1)
            result ^= arr[i];
    }
    return result;
}

int main() {
    int arr[] = {1, 3, 6, 8};
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << "XOR của tất cả XOR con mảng: " << xorSubarrayXors(arr, N);
    return 0;
}

Kết quả

XOR của tất cả XOR con mảng: 0