Giả sử chúng ta có một mảng n phần tử; chúng ta phải tìm số cặp trong mảng mà XOR của chúng bằng 0. Cặp (x, y) có XOR bằng 0 thì x = y. Để giải quyết nó, chúng ta có thể sắp xếp mảng, sau đó nếu hai phần tử liên tiếp giống nhau thì tăng bộ đếm. Nếu tất cả các phần tử giống nhau, thì bộ đếm cuối cùng có thể không được đếm. Trong trường hợp đó, chúng ta sẽ kiểm tra xem phần tử cuối và phần tử đầu có giống nhau hay không, nếu giống thì tăng bộ đếm thêm 1.
Ví dụ
#include<iostream> #include<algorithm> using namespace std; int countPairs(int arr[], int n) { int count = 0; sort(arr, arr+n); for(int i = 0; i<n - 1; i++){ if(arr[i] == arr[i+1]){ count++; } } if(arr[0] == arr[n-1]) count++; return count; } int main() { int arr[] = {1, 2, 1, 2, 4}; int n = sizeof(arr)/sizeof(arr[0]); cout << "Number of pairs: " << countPairs(arr, n); }
Kết quả
Number of pairs: 2