Đếm tất cả cặp có XOR cho trước trong C++

Trong hướng dẫn này, ta sẽ thảo luận chương trình để tìm số lượng cặp có XOR cho trước.

Cho một mảng và giá trị X. Nhiệm vụ là tìm số cặp (i, j) sao cho arr[i] ^ arr[j] = X.

Ví dụ

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

int count_pair(int arr[], int n, int x) {
    int result = 0;
    unordered_map<int, int> m;
    for(int i = 0; i < n; i++) {
        int curr_xor = x ^ arr[i];
        if(m.find(curr_xor) != m.end())
            result += m[curr_xor];
        m[arr[i]]++;
    }
    return result;
}

int main() {
    int arr[] = {2, 5, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 0;
    cout << "Count of pairs with given XOR = " << count_pair(arr, n, x);
    return 0;
}

Kết quả

Count of pairs with given XOR = 1