Tuesday, 19 Oct 2021

# 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