Count all pairs with given XOR - GeeksforGeeks

Count all pairs with given XOR - GeeksforGeeks
Given an array of +ve integers and a number x, find the number of pairs of integers in the array whose XOR is equal to x.

A Simple solution is to traverse each element and check if there’s another number whose XOR with it is equal to x. This solution takes O(n2) time.

An efficient solution of this problem take O(n) time. The idea is based on the fact that arr[i] ^ arr[j] is equal to x if and only if arr[i] ^ x is equal to arr[j].

1) Initialize result as 0.
2) Create an empty hash set "s".
3) Do following for each element arr[i] in arr[]
   (a) If x ^ arr[i] is in "s", then increment result by 1.
   (b) Insert arr[i] into the hash set "s".
3) return result.

int xorPairCount(int arr[], int n, int x)

{

    int result = 0; // Initialize result

 

    // create empty set that stores the visiting

    // element of array.

    // Refer below post for details of unordered_set

    // http://www.geeksforgeeks.org/unorderd_set-stl-uses/

    int unordered_set<int> s;

 

    for (int i=0; i<n ; i++)

    {

        // If there exist an element in set s

        // with XOR equals to x^arr[i], that means

        // there exist an element such that the

        // XOR of element with arr[i] is equal to

        // x, then increment count.

        if (s.find(k^arr[i] != s.end())

            result++;

 

        // Make element visited

        s.insert(arr[i]);

    }

 

    // return total count of xorPairCount = k

    return result;

}

Read full article from Count all pairs with given XOR - GeeksforGeeks