In the article, we are going to discuss one of the popular questions which to find the number of pairs in an array such that their XOR is 0.
Problem Statement
Suppose you have been given an array of N integers. You need to find the number of pairs(i, j) that will satisfy the below condition:
arr[i] XOR arr[j] = 0 and 1<=i<j<=n
This states that you need to find the number of pairs present in the array that satisfy the above condition. With the below example, the explanation you are going to understand the problem statement much better.
Example
Input
arr[] = {1, 3, 4, 1, 4}
Output
2
Explanation: (0, 3) contains element 1 at both position, so XOR of same element will going to be 0, and similarly, (2, 4) contains element 4 at both position, so XOR of both will going to be 0.
Brute Force Approach
Firstly, we will sort the given array and then count the frequency of each element.
Combinatorics allows us to see that if an element's frequency is count, it will add count*(count-1)/2 to the solution.
Algorithm using the hash table
We need to calculate the frequency of each element in the input array. The frequency of each element can be counted using the index mapping technique.
Combinatorics allows us to see that if an element's frequency is count, it will add count*(count-1)/2 to the solution.
C++ Code
/* 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 count the required condition */
int calculate(int a[], int n){
/* retrieving maximum element of the array */
int *maximum = max_element(a, a + n);
int frequency[*maximum + 1] = {0};
/* Traversing through the list */
for(int i = 0; i < n; i++)
{
/* Counting how often each element occurs */
frequency[a[i]] += 1;
}
int answer = 0;
/* Traversing through the frequency list */
for(int i = 0; i < (*maximum)+1; i++)
{
answer = answer + frequency[i] * (frequency[i] - 1) ;
}
return answer/2;
}
/* Main program */
int main()
{
/* Input array */
int arr[] = { 1, 3, 4, 1, 4 };
/* Size of an input array */
int n = sizeof(arr) / sizeof(arr[0]);
/* Printing required output */
cout << calculate(arr, n);
return 0;
}
You can also try this code with Online C++ Compiler
/* Java implementation to find the number of pairs in an array such that their XOR is 0 */
import java.util.*;
class Main {
/* function to count the required condition */
static int calculate(int a[], int n)
{
/* retrieving maximum element of the array */
int maximum = Arrays.stream(a).max().getAsInt();
int frequency[] = new int[maximum + 1];
/* Traversing through the list */
for (int i = 0; i < n; i++)
{
/* Counting how often each element occurs */
frequency[a[i]] += 1;
}
int answer = 0;
/* Traversing through the frequency list */
for (int i = 0; i < (maximum) + 1; i++)
{
answer = answer + frequency[i] * (frequency[i] - 1);
}
return answer / 2;
}
/* Main program */
public static void main(String[] args)
{
/* Input array */
int arr[] = { 1, 3, 4, 1, 4 };
/* Size of an input array */
int n = arr.length;
/* Printing required output */
System.out.println(calculate(arr, n));
}
}
You can also try this code with Online Java Compiler
A hash table associates various keys with various values. Hash table implements the map, the serializable, and cloneable interfaces and inherits the dictionary type.
What are the hash table's three fundamental operations?
The fundamental principle operations of a hash table are: search which searches for an element in the hash table, Insert which adds a new element to the hash table, and Delete which removes an element from the hash table.
What is the time complexity of a hash table?
No matter how many entries are in the table, hash tables typically offer constant-time O(1) lookup. The majority of hash table schemes have an O(n) worst-case lookup time.
What is the load factor of a hash table?
Load factor can be defined as (m/n), where m is the preferred number of entries that can be added before the size of the underlying data structure needs to be increased and n is the overall size of the hash table.
How come hash tables are quick?
The linear time complexity of O(n) is required when searching through an array-like data structure that is the search time grows linearly in proportion to the size of the data structure. Simply, searching through an array is slower than using a hash table.
38+ registered 
