Count ordered pairs of Array elements such that bitwise AND of K and XOR of the pair is 0

Improve Article

Save Article

Like Article

Given an array arr[] of size N and an integer K, the task is to find the count of all the ordered pairs (i, j) where i != j, such that ((arr[i] ⊕ arr[j]) & K) = 0. The ⊕ represents bitwise XOR and & represents bitwise AND.

Examples:

Input: arr = [1, 2, 3, 4, 5], K = 3
Output: 2
Explanation: There are 2 pairs satisfying the condition. 
These pairs are: (1, 5) and (5, 1)

Input: arr = [5, 9, 24], K = 7
Output: 0
Explanation: No such pair satisfying the condition exists.

Approach: The given problem can be solved with the help of the following idea:

Using distributive property, we can write ((arr[i] ⊕ arr[j]) & K) = ((arr[i] & K) ⊕ (arr[j] & K)). 
Since for ((arr[i] & K) ⊕ (arr[j] & K)) = 0, these two terms (arr[i] & K) and (arr[j] & K) must be equal.

Follow the below steps to solve the problem:

  • Create a map and an answer variable (say Res = 0).
  • Traverse the array and insert (arr[i] & K) to map with its count.
  • Now, traverse the map and for each entry if there are X such occurrences then possible pairs = X*(X-1). So add that to the value Res.
  • Return Res as the required answer.

Below is the implementation of the above approach:

C++

  

#include <bits/stdc++.h>

using namespace std;

  

int findPair(int* arr, int N, int K)

{

    map<int, int> Mp;

    int Res = 0;

  

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

        Mp[arr[i] & K]++;

  

    for (auto i : Mp)

        Res += ((i.second - 1) * i.second);

  

    return Res;

}

  

int main()

{

    int arr[] = { 1, 2, 3, 4, 5 };

    int N = sizeof(arr) / sizeof(arr[0]);

    int K = 3;

  

    

    cout << findPair(arr, N, K) << endl;

    return 0;

}

Time Complexity: O(N)
Auxiliary Space: O(N)

By Julio MarchiPosted on