XOR 為零的唯一三元組數 · GeeksForGeeks 中文系列教程

# XOR 為零的唯一三元組數 > 原文： [https://www.geeksforgeeks.org/number-unique-triplets-whose-xor-zero/](https://www.geeksforgeeks.org/number-unique-triplets-whose-xor-zero/) 給定 N 個沒有重復的數字，請計算唯一三元組**（ i ， j ， k ）**的數量 XOR 為 0。如果三元組中的所有三個數字都是唯一的，則說三元組是唯一的。 **示例**： ``` Input : a[] = {1, 3, 5, 10, 14, 15}; Output : 2 Explanation : {1, 14, 15} and {5, 10, 15} are the unique triplets whose XOR is 0\. {1, 14, 15} and all other combinations of 1, 14, 15 are considered as 1 only. Input : a[] = {4, 7, 5, 8, 3, 9}; Output : 1 Explanation : {4, 7, 3} is the only triplet whose XOR is 0 ``` **樸素的方法**：樸素的方法是運行三個嵌套循環，第一個從 0 到 n，第二個從 i + 1 到 n，最后一個從 j + 1 到 n，以獲得唯一的三元組。計算 i ， j ， k 的 XOR，檢查其是否等于 0，如果等于 0，則增加計數。時間復雜度：O（n 3 ） **有效方法**：一種有效方法是使用兩個相同數字的 XOR 等于 0 的 XOR 屬性之一。因此，我們僅需要計算唯一對的 XOR，并且如果計算出的 XOR 是數組元素，則得到 XOR 為 0 的三元組。以下是計算唯一三元組數的步驟：以下是此方法的完整算法： 1. 使用 map 標記所有數組元素。 2. 運行兩個嵌套循環，一個來自 i-n，另一個來自 i + 1-n，以獲取所有對。 3. 獲得對的異或。 4. 檢查 XOR 是否為數組元素，而不是 i 或 j 之一。 5. 如果條件成立，請增加計數。 6. 返回 count / 3，因為我們只需要唯一的三元組。由于 i-n 和 j + 1-n 給我們唯一的對而不是三胞胎，所以我們做一個 count / 3 來刪除其他兩個可能的組合。以下是上述想法的實現： ## C++ ```cpp // CPP program to count the number of // unique triplets whose XOR is 0 #include <bits/stdc++.h> using namespace std; // function to count the number of? // unique triplets whose xor is 0 int countTriplets(int a[], int n)? { ????// To store values that are present ????unordered_set<int> s; ????for (int i = 0; i < n; i++) ????????s.insert(a[i]); ????// stores the count of unique triplets ????int count = 0; ????// traverse for all i, j pairs such that j>i ????for (int i = 0; i < n; i++) { ????????for (int j = i + 1; j < n; j++) { ??????????// xor of a[i] and a[j] ??????????int xr = a[i] ^ a[j]; ??????????// if xr of two numbers is present,? ??????????// then increase the count ??????????if (s.find(xr) != s.end() && xr != a[i] &&? ???????????????????????????????????????xr != a[j]) ????????????count++; ????????} ????} ????// returns answer ????return count / 3; } // Driver code to test above function int main()? { ????int a[] = {1, 3, 5, 10, 14, 15}; ????int n = sizeof(a) / sizeof(a[0]);??? ????cout << countTriplets(a, n);???? ????return 0; } ```