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 = 2
Output: 2
Explanation: The pairs satisfying the necessary conditions are {{3, 0}, {0, 5}}.Input: arr[] = {1, 2, 3, 4}, M = 3
Output: 3
Explanation: 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.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find total count of// given pairs satisfying the equationint countPairs(int a[], int N, int M){ // Initialize the count to 0 int count = 0; // Loop through the array for (int i = 0; i < N; i++) { // Loop through the remaining // elements of the array for (int j = i + 1; j < N; j++) { // Calculate the XOR of // the pair elements int x = a[i] ^ a[j]; // Calculate the AND of // the pair elements int y = a[i] & a[j]; // Check if the condition is satisfied // __builtin_popcount() returns no. of set bits if (__builtin_popcount(x) + 2 * __builtin_popcount(y) == M) { // increment the count count++; } } } // Return the count of pairs // satisfying the condition return count;}// Driver codeint main(){ int arr[] = { 3, 0, 4, 5 }; int N = sizeof(arr) / sizeof(arr[0]); int M = 2; // Function Call cout << countPairs(arr, N, M) << endl; return 0;} |
Java
// Java codeimport java.io.*;import java.util.*;public class CountPairs { // Function to find the total count of // given pairs satisfying the equation static int countPairs(int[] a, int N, int M) { // Initialize the count to 0 int count = 0; // Loop through the array for (int i = 0; i < N; i++) { // Loop through the remaining // elements of the array for (int j = i + 1; j < N; j++) { // Calculate the XOR of the pair elements int x = a[i] ^ a[j]; // Calculate the AND of the pair elements int y = a[i] & a[j]; // Check if the condition is satisfied // Integer.bitCount() returns the number of set bits if (Integer.bitCount(x) + 2 * Integer.bitCount(y) == M) { // Increment the count count++; } } } // Return the count of pairs satisfying the condition return count; } // Driver code public static void main(String[] args) { int arr[] = { 3, 0, 4, 5 }; int N = arr.length; int M = 2; // Function Call System.out.println(countPairs(arr, N, M)); }}// This code is contributed by guptapratik |
Python3
# Python3 Program for the above approach# Function to count number of setbits in the number ndef countSetBits(n): # Stores the count of setbits count = 0 # Iterate while N is greater than 0 while (n): # Increment count by 1 if N is odd count += n & 1 # Right shift N n >>= 1 # Return the count of set bits return count# Function to find total count of# given pairs satisfying the equationdef countPairs(a, N, M): #Initialize the count to 0 count = 0 #Loop through the array for i in range(0,N): #Loop through the remaining #elements of the array for j in range(i+1,N): # Calculate the XOR of the pair elements x = a[i] ^ a[j] # Calculate the AND of the pair elements y = a[i] & a[j] if (countSetBits(x) + 2 * countSetBits(y))== M: #increment the count count+=1 # Return the count of pairs satisfying the condition return count arr = [ 3, 0, 4, 5]N = len(arr)M = 2# Function callpairs=countPairs(arr, N, M)print(pairs) |
C#
using System;namespace CountPairs {class Program { // Function to find total count of // given pairs satisfying the equation static int CountPairs(int[] a, int N, int M) { // Initialize the count to 0 int count = 0; // Loop through the array for (int i = 0; i < N; i++) { // Loop through the remaining // elements of the array for (int j = i + 1; j < N; j++) { // Calculate the XOR of // the pair elements int x = a[i] ^ a[j]; // Calculate the AND of // the pair elements int y = a[i] & a[j]; // Check if the condition is satisfied // CountSetBits() returns no. of set bits if (CountSetBits(x) + 2 * CountSetBits(y) == M) { // increment the count count++; } } } // Return the count of pairs // satisfying the condition return count; } // Function to count the number of set bits static int CountSetBits(int num) { int count = 0; while (num > 0) { count += num & 1; num >>= 1; } return count; } // Driver code static void Main(string[] args) { int[] arr = { 3, 0, 4, 5 }; int N = arr.Length; int M = 2; // Function Call Console.WriteLine(CountPairs(arr, N, M)); }}} |
Javascript
// Function to find total count of// given pairs satisfying the equationfunction countPairs(arr, M) { // Initialize the count to 0 let count = 0; // Loop through the array for (let i = 0; i < arr.length; i++) { // Loop through the remaining // elements of the array for (let j = i + 1; j < arr.length; j++) { // Calculate the XOR of the pair elements let x = arr[i] ^ arr[j]; // Calculate the AND of the pair elements let y = arr[i] & arr[j]; // Check if the condition is satisfied if (popcount(x) + 2 * popcount(y) === M) { // increment the count count++; } } } // Return the count of pairs satisfying the condition return count;}// Helper function to count the number of set bits in a numberfunction popcount(num) { let count = 0; while (num > 0) { count += num & 1; num >>= 1; } return count;}// Driver codelet arr = [3, 0, 4, 5];let M = 2;// Function Callconsole.log(countPairs(arr, M)); |
Output:
2
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:
- First, traverse the array arr[].
- For every array element arr[i], update arr[i] with the count of set bits present in it.
- Now print the count of pairs from the array whose sum is equal to M.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to count number// of setbits in the number nint countsetbits(int n){ // Stores the count of setbits int count = 0; // Iterate while N is // greater than 0 while (n) { // Increment count by 1 // if N is odd count += n & 1; // Right shift N n >>= 1; } // Return the count of set bits return (count);}// Function to find total count of// given pairs satisfying the equationint countPairs(int a[], int N, int M){ for (int i = 0; i < N; i++) { // Update arr[i] with the count // of set bits of arr[i] a[i] = countsetbits(a[i]); } // Stores the frequency // of each array element unordered_map<int, int> mp; // Traverse the array for (int i = 0; i < N; i++) { // Increment the count // of arr[i] in mp mp[a[i]]++; } // Stores the total count of pairs int count = 0; // Traverse the array arr[] for (int i = 0; i < N; i++) { // Increment count by mp[M - a[i]] count += mp[M - a[i]]; // If a[i] is equal to M-a[i] if (a[i] == M - a[i]) { // Decrement count by 1 count--; } } // Return count/2 return (count / 2);}// Driver Codeint main(){ // Input int arr[] = { 3, 0, 4, 5 }; int N = sizeof(arr) / sizeof(arr[0]); int M = 2; cout << countPairs(arr, N, M);} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG{// Function to count number// of setbits in the number nstatic int countsetbits(int n){ // Stores the count of setbits int count = 0; // Iterate while N is // greater than 0 while (n != 0) { // Increment count by 1 // if N is odd count += n & 1; // Right shift N n >>= 1; } // Return the count of set bits return (count);}// Function to find total count of// given pairs satisfying the equationstatic int countPairs(int[] a, int N, int M){ for(int i = 0; i < N; i++) { // Update arr[i] with the count // of set bits of arr[i] a[i] = countsetbits(a[i]); } // Stores the frequency // of each array element HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); // Traverse the array for (int i = 0; i < N; i++) { if (mp.containsKey(a[i])) { mp.put(a[i], mp.get(a[i]) + 1); } else { mp.put(a[i], 1); } } // Stores the total count of pairs int count = 0; // Traverse the array arr[] for(int i = 0; i < N; i++) { // Increment count by mp[M - a[i]] count += mp.get(M - a[i]); // If a[i] is equal to M-a[i] if (a[i] == M - a[i]) { // Decrement count by 1 count--; } } // Return count/2 return (count / 2);} // Driver Codepublic static void main(String[] args){ // Input int[] arr = { 3, 0, 4, 5 }; int N = arr.length; int M = 2; System.out.println(countPairs(arr, N, M));}}// This code is contributed by avijitmondal1998 |
Python3
# Python3 Program for the above approach# Function to count number# of setbits in the number ndef countSetBits(n): # Stores the count of setbits count = 0 # Iterate while N is # greater than 0 while (n): # Increment count by 1 # if N is odd count += n & 1 # Right shift N n >>= 1 # Return the count of set bits return countdef countPairs(arr, N, M): for i in range(0, N): # Update arr[i] with the count # of set bits of arr[i] arr[i] = countSetBits(arr[i]) # Store counts of all elements in a dictionary mp = {} for i in range(0, N): if arr[i] in mp: mp[arr[i]] += 1 else: mp[arr[i]] = 1 twice_count = 0 # Iterate through each element and increment # the count (Notice that every pair is # counted twice) for i in range(0, N): if M - arr[i] in mp.keys(): twice_count += mp[M - arr[i]] # if (arr[i], arr[i]) pair satisfies the # condition, then we need to ensure that # the count is decreased by one such # that the (arr[i], arr[i]) pair is not # considered if (M - arr[i] == arr[i]): twice_count -= 1 # return the half of twice_count return int(twice_count / 2) # Driver code# Inputarr = [ 3, 0, 4, 5]N = len(arr)M = 2print(countPairs(arr, N, M))# This code is contributed by santhoshcharan. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to count number// of setbits in the number nstatic int countsetbits(int n){ // Stores the count of setbits int count = 0; // Iterate while N is // greater than 0 while (n != 0) { // Increment count by 1 // if N is odd count += n & 1; // Right shift N n >>= 1; } // Return the count of set bits return (count);}// Function to find total count of// given pairs satisfying the equationstatic int countPairs(int[] a, int N, int M){ for(int i = 0; i < N; i++) { // Update arr[i] with the count // of set bits of arr[i] a[i] = countsetbits(a[i]); } // Stores the frequency // of each array element Dictionary<int, int> mp = new Dictionary<int, int>(); // Traverse the array for(int i = 0; i < N; ++i) { // Update frequency of // each array element if (mp.ContainsKey(a[i]) == true) mp[a[i]] += 1; else mp[a[i]] = 1; } // Stores the total count of pairs int count = 0; // Traverse the array arr[] for(int i = 0; i < N; i++) { // Increment count by mp[M - a[i]] count += mp[M - a[i]]; // If a[i] is equal to M-a[i] if (a[i] == M - a[i]) { // Decrement count by 1 count--; } } // Return count/2 return (count / 2);}// Driver Codestatic public void Main(){ // Input int[] arr = { 3, 0, 4, 5 }; int N = arr.Length; int M = 2; Console.WriteLine(countPairs(arr, N, M));}}// This code is contributed by sanjoy_62 |
Javascript
<script>// Javascript program for the above approach// Function to count number// of setbits in the number nfunction countsetbits(n){ // Stores the count of setbits var count = 0; // Iterate while N is // greater than 0 while (n) { // Increment count by 1 // if N is odd count += n & 1; // Right shift N n >>= 1; } // Return the count of set bits return (count);}// Function to find total count of// given pairs satisfying the equationfunction countPairs(a, N, M){ for (var i = 0; i < N; i++) { // Update arr[i] with the count // of set bits of arr[i] a[i] = countsetbits(a[i]); } // Stores the frequency // of each array element var mp = new Map(); // Traverse the array for (var i = 0; i < N; i++) { // Increment the count // of arr[i] in mp if(mp.has(a[i])) mp.set(a[i], mp.get(a[i])+1) else mp.set(a[i], 1) } // Stores the total count of pairs var count = 0; // Traverse the array arr[] for (var i = 0; i < N; i++) { // Increment count by mp[M - a[i]] count += mp.get(M - a[i]); // If a[i] is equal to M-a[i] if (a[i] == M - a[i]) { // Decrement count by 1 count--; } } // Return count/2 return (count / 2);}// Driver Code// Inputvar arr = [3, 0, 4, 5];var N = arr.length;var M = 2;document.write( countPairs(arr, N, M));</script> |
Output
2
Time Complexity: O(NlogN)
Auxiliary Space: O(N) as using auxiliary space for unordered_map
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
