Saturday, 23 Oct 2021

# Count of pairs {X, Y} from an array such that sum of count of set bits in X ⊕ Y and twice the count of set bits in X & Y is M

Count of pairs {X, Y} from an array such that sum of count of set bits in X ⊕ Y and twice the count of set bits in X & Y is M
Given an array arr[] consisting of N non-negative integers and an integer M, the task is to find the count of unordered pairs {X, Y} of array elements that satisfies the condition setBits(X ⊕ Y) + 2 * setBits(X & Y) = M, where ⊕ denotes the Bitwise XOR and & denotes the Bitwise AND.
Examples:

Input: arr[] = {30, 0, 4, 5 }, M = 2Output: 2Explanation: The pairs satisfying the necessary conditions are {{3, 0}, {0, 5}}.
Input: arr[] = {1, 2, 3, 4}, M = 3Output: 3Explanation: The pairs satisfying the necessary conditions are {{1, 3}, {2, 3}, {3, 4}}.

Naive Approach: The simplest approach is to generate all possible pairs from the given array and for each pair, check if the necessary condition is satisfied or not. Increment the count for pairs satisfying the given conditions and finally, print the count of pairs.Time Complexity: O(N2)Auxiliary Space: O(1)
Efficient Approach: The above approach can be optimized based on the following observations:
From the property of Bitwise XOR:
setBits( a⊕ b ) = setBits( a|b ) – setBits( a&b )
setBits( a|b ) = setBits(a) + setBits(b) – setBits( a&b )

Therefore, the given equation becomes:
( setBits( X|Y ) – setBits( X&Y ) )+( 2 × setBits( X&Y ) ) = M
setBits( X ) + setBits ( Y ) – setBits( X&Y ) – setBits( X&Y ) + ( 2 × setBits ( X&Y ) ) = M
setBits( X ) + setBits( Y ) = M

Therefore, the task reduces to counting the pairs of elements whose sum of set bits is equal to M.

Follow the steps below to solve the problem:
Below is the implementation of the above approach:

C++

#include
using namespace std;

int countsetbits(int n)
{

int count = 0;

while (n) {

count += n & 1;

n >>= 1;
}

return (count);
}

int countPairs(int a[], int N, int M)
{

for (int i = 0; i < N; i++) {                              a[i] = countsetbits(a[i]);     }                  unordered_map mp;             for (int i = 0; i < N; i++) {                              mp[a[i]]++;     }             int count = 0;             for (int i = 0; i < N; i++) {                     count += mp[M - a[i]];                     if (a[i] == M - a[i]) {                             count--;         }     }             return (count / 2); }    int main() {          int arr[] = { 3, 0, 4, 5 };     int N = sizeof(arr) / sizeof(arr);     int M = 2;        cout