Find number of pairs in an array such that their XOR is 0
Given an array of size N. Find the number of pairs (i, j) such that XOR = 0, and 1 <= i < j <= N.
Examples :
Input : A[] = {1, 3, 4, 1, 4} Output : 2 Explanation : Index (0, 3) and (2, 4) Input : A[] = {2, 2, 2} Output : 3
First Approach : Sorting
XOR = 0 is only satisfied when . Therefore, we will first sort the array and then count the frequency of each element. By combinatorics, we can observe that if frequency of some element is then, it will contribute to the answer.
Below is the implementation of above approach:
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]); cout << calculate(a, n); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
C
// C program to find number of pairs in an array such that // their XOR is 0 #include <stdio.h> #include <stdlib.h> int cmpfunc( const void * a, const void * b) { return (*( int *)a - *( int *)b); } // Function to calculate the count int calculate( int a[], int n) { // Sorting the list using built in function qsort (a, n, sizeof ( int ), cmpfunc); 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]); printf ( "%d" , calculate(a, n)); return 0; } // This code is contributed by Aditya Kumar (adityakumar129) |
Java
// Java program to find number of pairs in an array suchthat // 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 ; for ( int i = 1 ; i < n; i++) { // Counting frequency of each elements if (a[i] == a[i - 1 ]) 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; System.out.println(calculate(a, n)); } } // This code is contributed by Aditya Kumar (adityakumar129) |
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> |
Output
2
Time Complexity : O(N Log N)
Auxiliary Space: O(1), as no extra space is used
Second Approach: Hashing (Index Mapping)
Solution is handy, if we can count the frequency of each element in the array. Index mapping technique can be used to count the frequency of each element.
Below is the implementation of above approach :
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> |
Output
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Note : Index Mapping method can only be used when the numbers in the array are not large. In such cases, sorting method can be used.