查找数组中的对数，使其XOR为0-yiteyi-C++库

给定一个数组 $A[ ]$ 大小为N。求出配对数（i，j），使 $A_i$ 异或 $A_j$ =0，1<=i 例如：

null

Input : A[] = {1, 3, 4, 1, 4}Output : 2Explanation : Index (0, 3) and (2, 4)Input : A[] = {2, 2, 2}Output : 3

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

第一种方法 : 分类 $A_i$ 异或 $A_j$ =0仅在以下情况下满足： $A_i = A_j$ .因此，我们将首先对数组进行排序，然后计算每个元素的频率。通过组合数学，我们可以观察到，如果某个元素的频率是 $count$ 然后，它将做出贡献 $count*(count-1)/2$ 答案是肯定的。以下是上述方法的实施情况：

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                       
                         // 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 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

                         # 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 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                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                   
                                                 a                                     =                                     [                                     1                                     ,                                     2                                     ,                                     1                                     ,                                     2                                     ,                                     4                                     ]                       
           
                                                 # Print the count                       
                                                 print                                     (calculate(a))                       

C#

                         // 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 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.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript 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                       
                                                 a.sort();                       
           
                                                 let count = 1;                       
                                                 let answer = 0;                       
           
                                                 // Traversing through the                       
                                                 // elements                       
                                                 for                                     (let 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 + Math.floor((count * (count - 1)) / 2);                       
                                                 count = 1;                       
                                                 }                       
                                                 }                       
           
                                                 answer = answer + Math.floor((count * (count - 1)) / 2);                       
           
                                                 return                                     answer;                       
                         }                       
           
                         // Driver Code                       
           
                                                 let a = [ 1, 2, 1, 2, 4 ];                       
                                                 let n = a.length;                       
           
                                                 // Print the count                       
                                                 document.write(calculate(a, n));                       
           
                         // This code is contributed by Surbhi Tyagi.                       
           
                         </script>                       

输出：

时间复杂性 ：O（N日志N） 第二种方法 : 散列（索引映射） 如果我们能计算数组中每个元素的频率，这个解决方案就很方便了。索引映射技术可以用来计算每个元素的频率。以下是上述方法的实施情况：

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 + n);                       
           
                                                 // 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                       

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 answer                       
                                                 static                                     int                                     calculate(                                     int                                     a[],                                     int                                     n)                       
                                                 {                       
           
                                                 // Finding the maximum of the array                       
                                                 int                                     maximum = Arrays.stream(a).max().getAsInt();                       
           
                                                 // Creating frequency array                       
                                                 // With initial value 0                       
                                                 int                                     frequency[] =                                     new                                     int                                     [maximum +                                     1                                     ];                       
           
                                                 // 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                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     a[] = {                                     1                                     ,                                     2                                     ,                                     1                                     ,                                     2                                     ,                                     4                                     };                       
                                                 int                                     n = a.length;                       
           
                                                 // Function calling                       
                                                 System.out.println(calculate(a, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by 29AjayKumar                       

Python 3

                         # Python3 program to find number of pairs                       
                         # in an array such that their XOR is 0                       
           
                         # Function to calculate the answer                       
                         def                                     calculate(a) :                       
                                   
                                                 # Finding the maximum of the array                       
                                                 maximum                                     =                                     max                                     (a)                       
                                   
                                                 # Creating frequency array                       
                                                 # With initial value 0                       
                                                 frequency                                     =                                     [                                     0                                     for                                     x                                     in                                     range                                     (maximum                                     +                                     1                                     )]                       
                                   
                                                 # Traversing through the array                       
                                                 for                                     i                                     in                                     a :                       
                                   
                                                 # Counting frequency                       
                                                 frequency[i]                                     +                                     =                                     1                       
                                   
                                                 answer                                     =                                     0                       
                                   
                                                 # Traversing through the frequency array                       
                                                 for                                     i                                     in                                     frequency :                       
                                   
                                                 # Calculating answer                       
                                                 answer                                     =                                     answer                                     +                                     i                                     *                                     (i                                     -                                     1                                     )                                     /                                     /                                     2                       
                                   
                                                 return                                     answer                       
           
                         # Driver Code                       
                         a                                     =                                     [                                     1                                     ,                                     2                                     ,                                     1                                     ,                                     2                                     ,                                     4                                     ]                       
                         print                                     (calculate(a))                       

C#

                         // C# program to find number of pairs                       
                         // in an array such that their XOR is 0                       
                         using                                     System;                       
                         using                                     System.Linq;                       
                         class                                     GFG                       
                         {                       
           
                                                 // Function to calculate the answer                       
                                                 static                                     int                                     calculate(                                     int                                     []a,                                     int                                     n)                       
                                                 {                       
           
                                                 // Finding the maximum of the array                       
                                                 int                                     maximum = a.Max();                       
           
                                                 // Creating frequency array                       
                                                 // With initial value 0                       
                                                 int                                     []frequency =                                     new                                     int                                     [maximum + 1];                       
           
                                                 // 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                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 int                                     []a = {1, 2, 1, 2, 4};                       
                                                 int                                     n = a.Length;                       
           
                                                 // Function calling                       
                                                 Console.WriteLine(calculate(a, n));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by PrinciRaj1992                       

PHP

                         <?php                       
                         // PHP program to find number                       
                         // of pairs in an array such                       
                         // that their XOR is 0                       
           
                         // Function to calculate the answer                       
                         function                                     calculate(                                     $a                                     ,                                     $n                                     )                       
                         {                       
                                   
                                                 // Finding the maximum of the array                       
                                                 $maximum                                     = max(                                     $a                                     );                       
                                   
                                                 // Creating frequency array                       
                                                 // With initial value 0                       
                                                 $frequency                                     =                                     array_fill                                     (0,                                     $maximum                                     + 1, 0);                       
                                   
                                                 // Traversing through the array                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 {                       
                                                 // Counting frequency                       
                                                 $frequency                                     [                                     $a                                     [                                     $i                                     ]] += 1;                       
                                                 }                       
                                                 $answer                                     = 0;                       
                                   
                                                 // Traversing through                       
                                                 // the frequency array                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     < (                                     $maximum                                     ) + 1;                                     $i                                     ++)                       
                                                 {                       
                                                 // Calculating answer                       
                                                 $answer                                     =                                     $answer                                     +                                     $frequency                                     [                                     $i                                     ] *                       
                                                 (                                     $frequency                                     [                                     $i                                     ] - 1);                       
                                                 }                       
                                                 return                                     $answer                                     / 2;                       
                         }                       
           
                         // Driver Code                       
                         $a                                     =                                     array                                     (1, 2, 1, 2, 4);                       
                         $n                                     =                                     count                                     (                                     $a                                     );                       
                         // Function calling                       
                         echo                                     (calculate(                                     $a                                     ,                                     $n                                     ));                       
           
                         // This code is contributed by Smitha                       
                         ?>                       

Javascript

                         <script>                       
                         // Javascript program to find number of pairs                       
                         // in an array such that their XOR is 0                       
           
                         // Function to calculate the answer                       
                         function                                     calculate(a, n){                       
                                   
                                                 // Finding the maximum of the array                       
                                                 let maximum = Math.max(...a);                       
           
                                                 // Creating frequency array                       
                                                 // With initial value 0                       
                                                 let frequency =                                     new                                     Array(maximum + 1).fill(0);                       
                                   
                                                 // Traversing through the array                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 {                       
                                                 // Counting frequency                       
                                                 frequency[a[i]] += 1;                       
                                                 }                       
                                                 let answer = 0;                       
                                   
                                                 // Traversing through the frequency array                       
                                                 for                                     (let i = 0; i < maximum+1; i++)                       
                                                 {                       
                                                 // Calculating answer                       
                                                 answer = answer + frequency[i] * (frequency[i] - 1) ;                       
                                                 }                       
                                                 return                                     parseInt(answer/2);                       
                         }                       
           
                         // Driver Code                       
                                                 let a = [1, 2, 1, 2, 4];                       
                                                 let n = a.length;                       
                                   
                                                 // Function calling                       
                                                 document.write(calculate(a,n));                       
           
                         </script>                       

输出：

时间复杂性 ：O（N）注：索引映射方法只能在数组中的数字不大时使用。在这种情况下，可以使用排序方法。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章