Đếm bộ ba duy nhất có XOR = 0 trong mảng bằng C++

Cho mảng các số khác nhau. Đếm số bộ ba (x,y,z) khác nhau thỏa x ^ y ^ z = 0 (tức x ^ y = z). Ví dụ:

Input: {5,6,7,1,3} → 2 bộ ba: {5,6,3}, {6,7,1} Input: {3,6,8,1,5,4,12} → 3 bộ ba: {3,6,5}, {1,5,4}, {4,8,12}

Cách hiệu quả O(N²): Hash Set

Đưa tất cả phần tử vào unordered_set. Duyệt mọi cặp (i,j), tính XR = arr[i] ^ arr[j]. Nếu XR có trong set và khác arr[i], arr[j] → đếm++. Mỗi bộ ba được đếm 3 lần (3 hoán vị) → kết quả = count / 3.

Ví dụ

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

int main() {
    int arr[] = { 3, 6, 8, 1, 5, 4, 12 };
    int n = sizeof(arr) / sizeof(arr[0]);
    unordered_set<int> values;
    for (int i = 0; i < n; i++) values.insert(arr[i]);
    int count = 0;
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++) {
            int XR = arr[i] ^ arr[j];
            if (values.find(XR) != values.end() && XR != arr[i] && XR != arr[j])
                count++;
        }
    cout << "Number of unique triplets : " << count / 3;
    return 0;
}

Kết quả

Number of unique triplets : 3

Kết luận

Đếm bộ ba XOR = 0 trong mảng phần tử duy nhất: O(N²) dùng hash set, chia 3 để loại bỏ trùng hoán vị. Code C++.