# Count pairs from an array having sum of twice of their AND and XOR equal to K

Given an array arr[] consisting of N integers and an integer K, the task is to count the number of pairs satisfying the equation 2*(arr[i] & arr[j]) + (arr[i] ^ arr[j]) = K.

Examples:

Input: arr[] = {1, 5, 4, 8, 7}, K = 9Output: 2Explanation:

Elements at index 0 and 3, i.e. arr[i] = 1, arr[j] = 8, satisfies the given equations.

Elements at index 1 and 2, i.e. arr[i] = 5, arr[j] = 4, satisfies the given equations.

Input: arr[] = {1, 2, 2, 4, 5}, K = 3Output: 2

Naive Approach: The simplest approach is to generate all possible pairs from the array and for each pair, check if the pair satisfies the given equation or not.Time Complexity: O(N2)Auxiliary Space: O(1)

Efficient Approach: The above approach can be optimized based on the following observations:

Observation:

A + B = (A ^ B) + 2 * (A & B)

While calculating sum, if both bits are 1(i.e., AND is 1), the resultant bit is 0, and 1 is added as carry, which means every bit in AND is left-shifted by 1, i.e. value of AND is multiplied by 2 and added.

Therefore, A + B = given equations.

Hence, this verifies the above observation.

Follow the below steps to solve the problem:

The problem now reduces to Two Sum problem and the task reduces to count pairs whose sum is equal to K.

Initialize an unordered_map, say mp, and a variable, say cnt, to count the number of pairs satisfying the given conditions.

Traverse the array and for each element:

If mp[K – arr[i]] is not zero, then add its value to cnt.

Update the frequency of arr[i] in Map.

Print the cnt as the answer.

Below is the implementation of the above approach:

C++

#include

using namespace std;

void countPairs(int arr[], int N, int K)

{

unordered_map mp;

int cnt = 0;

for (int i = 0; i < N; i++) {
cnt += mp[K - arr[i]];
mp[arr[i]]++;
}
cout