# 查找數組中對的數量，以使它們的 XOR 為 0 > 原文： [https://www.geeksforgeeks.org/find-number-pairs-array-xor-0/](https://www.geeksforgeeks.org/find-number-pairs-array-xor-0/) 給定大小為 N 的數組![A[ ] ](https://img.kancloud.cn/f4/a5/f4a5c6b60e70dcecb9d2810436055aa9_32x28.png "Rendered by QuickLaTeX.com")。求對（i，j）的對數，以使 XOR  = 0，并且 1 < = i < j < =N。 **示例**： ``` Input : A[] = {1, 3, 4, 1, 4} Output : 2 Explanation : Index (0, 3) and (2, 4) Input : A[] = {2, 2, 2} Output : 3 ``` **第一種方法**： <font size="3">**排序**</font> 僅當時才滿足 XOR  = 0 的要求。 因此，我們將首先對數組進行排序，然后計算每個元素的頻率。 通過組合，我們可以觀察到，如果某個元素的頻率為，那么它將為答案提供。 以下是上述方法的實現： ## C++ ```cpp // C++ program to find number? // of pairs in an array such // that their XOR is 0 #include <bits/stdc++.h> using namespace std; // Function to calculate the // count int calculate(int a[], int n) { ????// Sorting the list using ????// built in function ????sort(a, a + n); ????int count = 1; ????int answer = 0; ????// Traversing through the ????// elements ????for (int i = 1; i < n; i++) { ????????if (a[i] == a[i - 1]){ ????????????// Counting frequency of each? ????????????// elements ????????????count += 1; ????????}? ????????else? ????????{ ????????????// Adding the contribution of ????????????// the frequency to the answer ????????????answer = answer + (count * (count - 1)) / 2; ????????????count = 1; ????????} ????} ????answer = answer + (count * (count - 1)) / 2; ????return answer; } // Driver Code int main() { ????int a[] = { 1, 2, 1, 2, 4 }; ????int n = sizeof(a) / sizeof(a[0]); ????// Print the count ????cout << calculate(a, n); ????return 0; } // This article is contributed by Sahil_Bansall. ``` ## Java ```java // Java program to find number? // of pairs in an array such // that their XOR is 0 import java.util.*; class GFG? { ????// Function to calculate? ????// the count ????static int calculate(int a[], int n) ????{ ????????// Sorting the list using ????????// built in function ????????Arrays.sort(a); ????????int count = 1; ????????int answer = 0; ????????// Traversing through the ????????// elements ????????for (int i = 1; i < n; i++)? ????????{ ????????????if (a[i] == a[i - 1]) ????????????{ ????????????????// Counting frequency of each? ????????????????// elements ????????????????count += 1; ????????????}? ????????????else ????????????{ ????????????????// Adding the contribution of ????????????????// the frequency to the answer ????????????????answer = answer + (count * (count - 1)) / 2; ????????????????count = 1; ????????????} ????????} ????????answer = answer + (count * (count - 1)) / 2; ????????return answer; ????} ????// Driver Code ????public static void main (String[] args)? ????{ ????????int a[] = { 1, 2, 1, 2, 4 }; ????????int n = a.length; ????????// Print the count ????????System.out.println(calculate(a, n)); ????} } // This code is contributed by Ansu Kumari. ``` ## Python3 ```py # Python3 program to find number of pairs # in an array such that their XOR is 0 # Function to calculate the count def calculate(a) : ????# Sorting the list using ????# built in function ????a.sort() ????count = 1 ????answer = 0 ????# Traversing through the elements ????for i in range(1, len(a)) : ????????if a[i] == a[i - 1] : ????????????# Counting frequncy of each elements ????????????count += 1 ????????else : ????????????# Adding the contribution of ????????????# the frequency to the answer ????????????answer = answer + count * (count - 1) // 2 ????????????count = 1 ????answer = answer + count * (count - 1) // 2 ????return answer # Driver Code if __name__ == '__main__': ????a = [1, 2, 1, 2, 4] ????# Print the count ????print(calculate(a)) ``` ## C# ```cs // C# program to find number? // of pairs in an array such // that their XOR is 0 using System; class GFG? { ????// Function to calculate? ????// the count ????static int calculate(int []a, int n) ????{ ????????// Sorting the list using ????????// built in function ????????Array.Sort(a); ????????int count = 1; ????????int answer = 0; ????????// Traversing through the ????????// elements ????????for (int i = 1; i < n; i++)? ????????{ ????????????if (a[i] == a[i - 1]) ????????????{ ????????????????// Counting frequency of each? ????????????????// elements ????????????????count += 1; ????????????}? ????????????else ????????????{ ????????????????// Adding the contribution of ????????????????// the frequency to the answer ????????????????answer = answer + (count * (count - 1)) / 2; ????????????????count = 1; ????????????} ????????} ????????answer = answer + (count * (count - 1)) / 2; ????????return answer; ????} ????// Driver Code ????public static void Main ()? ????{ ????????int []a = { 1, 2, 1, 2, 4 }; ????????int n = a.Length; ????????// Print the count ????????Console.WriteLine(calculate(a, n)); ????} } // This code is contributed by vt_m. ``` ## PHP ```php <?php // PHP program to find number? // of pairs in an array such // that their XOR is 0 // Function to calculate? // the count function calculate($a, $n) { ????// Sorting the list using ????// built in function ????sort($a); ????$count = 1; ????$answer = 0; ????// Traversing through the ????// elements ????for ($i = 1; $i < $n; $i++) ????{ ????????if ($a[$i] == $a[$i - 1]) ????????{ ????????????// Counting frequency of? ????????????// each elements ????????????$count += 1; ????????}? ????????else ????????{ ????????????// Adding the contribution of ????????????// the frequency to the answer ????????????$answer = $answer + ($count *? ???????????????????????($count - 1)) / 2; ????????????$count = 1; ????????} ????} ????$answer = $answer + ($count *? ???????????????($count - 1)) / 2; ????return $answer; } ????// Driver Code ????$a = array(1, 2, 1, 2, 4); ????$n = count($a); ????// Print the count ????echo calculate($a, $n); // This code is contributed by anuj_67\. ?> ``` **輸出**： ``` 2 ``` **時間復雜度**：`O(N log N)` ， **第二種方法**： <font size="3">**散列（索引映射）**</font> 如果我們可以計算數組中每個元素的頻率，則解決方案很方便。 索引映射技術可用于計算每個元素的頻率。 下面是上述方法的實現： ## C++ ``` // C++ program to find number of pairs // in an array such that their XOR is 0 #include <bits/stdc++.h> using namespace std; // Function to calculate the answer int calculate(int a[], int n){ ????// Finding the maximum of the array ????int *maximum = max_element(a, a + 5); ????// Creating frequency array ????// With initial value 0 ????int frequency[*maximum + 1] = {0}; ????// Traversing through the array? ????for(int i = 0; i < n; i++) ????{? ????????// Counting frequency ????????frequency[a[i]] += 1; ????} ????int answer = 0; ????// Traversing through the frequency array ????for(int i = 0; i < (*maximum)+1; i++) ????{? ????????// Calculating answer ????????answer = answer + frequency[i] * (frequency[i] - 1) ; ????} ????return answer/2; } // Driver Code int main() { ???int a[] = {1, 2, 1, 2, 4}; ???int n = sizeof(a) / sizeof(a[0]);? ???// Function calling ???cout << (calculate(a,n)); } // This code is contributed by Smitha ```