Find number of pairs in an array such that their XOR is 0

Difficulty Level Medium
Frequently asked in Cadence India CouponDunia Honeywell Indeed InfoEdge Moonfrog Labs Pinterest
Array Bits Hash Searching SortingViews 1427

The problem “Find number of pairs in an array such that their XOR is 0” state that supposes, we have given an array of integers. The problem statement asks to find out the number of pairs present in an array, which has the pair Ai XOR Aj = 0.

Note: 1 is less than or equal to i, i is less than j and j is less than or equal to n(1<=i < j<=n).

Example

Find number of pairs in an array such that their XOR is 0

arr[] = {2, 3, 1, 3, 2}
2

Explanation

Index (0,4) and (1,3).

arr[] = {1, 1, 1}
3

Algorithm

  1. Find out the maximum element present in an array.
  2. Create an array of size (maximum element).
  3. Traverse the array, while i < n (length of the array).
    1. Count and store the frequencies of each array element in the array we created.
  4. Traverse the count array, while i <= maximum element.
    1. Do output = output + count[i] * (count[i] – 1) ;
  5. Return output/2.

Explanation

We have an array of integers. The problem statement asks to find out the pair present in an array such that Ai XOR Aj = 0. We are going to use index mapping, which means we are going to count the frequency of each array element such that we can figure them out if they can do count[i]*count[i-1] and resultant into the output. To solve this use an array and in that place of array element which acts as an index of count array in which we are going to store our elements frequency, so if a number is found at a particular place, we are going to use it as an index.

We will found the maximum element from the array. And of that maximum element size, we are going to make an array, this is count array, this we are going to use as a frequency array. We need to traverse the array and store the count of each array element. Then we will set the output variable to 0.

Let us consider an example:

Example

arr[]={2, 3, 1, 3, 2} maximum size of array would be 3.

i=0, arr [i]=2, we will do count[arr[i]]+=1, it means 2nd index of count’s element will be increase by 1.

i=1, arr [i]=3, we will do count[arr[i]]+=1, it means 3nd index of count’s element will be increase by 1.

i=2, arr [i]=1, we will do count[arr[i]]+=1, it means 1st index of count’s element will be  increase by 1.

i=3, arr [i]=3, we will do count[arr[i]]+=1, it means 3rd index of count’s element will be increase by 1.

i=4, arr [i]=2, we will do count[arr[i]]+=1, it means 2nd index of count’s element will be increase by 1.

We have the count’s array as count[]={0,1,2,2}

We will traverse this array, and every time we do output = output + count[i] * (count[i] – 1).

And it will return the output as output/2.

C++ code to find number of pairs in an array such that their XOR is 0

#include<iostream>
#include<algorithm>

using namespace std;

int calculate(int a[], int n)
{
    int *maxm = max_element(a, a + 5);
    int count[*maxm + 1] = {0};

    for(int i = 0; i < n; i++)
    {
        count[a[i]] += 1;
    }
    int output = 0;
    for(int i = 0; i < (*maxm)+1; i++)
    {
        output = output + count[i] * (count[i] - 1) ;
    }
    return output/2;
}
int main()
{
    int a[] = {2, 3, 1, 3, 2};
    int n = sizeof(a) / sizeof(a[0]);
    cout <<"XOR Pairs are : "<< (calculate(a,n));
    return 0;
}

XOR Pairs are : 2

Java code to find number of pairs in an array such that their XOR is 0

import java.util.Arrays;

class XORPair
{
    public static int calculate(int arr[], int n)
    {
        int max= Arrays.stream(arr).max().getAsInt();

        int count[] = new int[max+ 1];

        for (int i = 0; i < n; i++)
        {
            count[arr[i]] += 1;
        }
        int output = 0;
        for (int i = 0; i < (max) + 1; i++)
        {
            output = output + count[i] * (count[i] - 1);
        }
        return output / 2;
    }
    public static void main(String[] args)
    {
        int a[] = {2, 3, 1, 3, 2};
        int n = a.length;
        System.out.println("XOR Pairs are : "+calculate(a, n));
    }
}

XOR Pairs are : 2

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. O(1) time is required for accessing the elements in the array. Thus the time complexity is linear.

Space Complexity

O(Max), where Max is the maximum element among all the elements in the array.

Translate »