Count of pairs in Array such that bitwise AND of XOR of pair and X is 0 - Coding

Given an array arr[] consisting of N positive integers and a positive integer X, the task is to find the number of pairs (i, j) such that i < j and (arr[i]^arr[j] )&X is 0.

Examples:

Input: arr[] = {1, 3, 4, 2}, X = 2
Output: 2
Explanation:
Following are the possible pairs from the given array:

(0, 2): The value of (arr[0]^arr[2])&X is (1^4)&2 = 0.

(1, 3): The value of (arr[1]^arr[3])&X is (3^2)&2 = 0.

Therefore, the total count of pairs is 2.

Input: arr[] = {3, 2, 5, 4, 6, 7}, X = 6
Output: 3

Naive Approach: The simple approach to solve the given problem is to generate all possible pairs of the given array and count those pairs (i, j) that satisfy the given criteria i.e., i < j and (arr[i]^arr[j] )&X is 0.. After checking for all the pairs, print the total count obtained.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of pairs
// that satisfy the given criteria i.e.,
// i < j and (arr[i]^arr[j] )&X is 0
int countOfPairs(int arr[], int N, int X)
{
    // Stores the resultant count
    // of pairs
    int count = 0;
 
    // Iterate over the range [0, N)
    for (int i = 0; i < N - 1; i++) {
 
        // Iterate over the range
        for (int j = i + 1; j < N; j++) {
 
            // Check for the given
            // condition
            if (((arr[i] ^ arr[j]) & X) == 0)
                count++;
        }
    }
 
    // Return the resultant count
    return count;
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 2, 5, 4, 6, 7 };
    int X = 6;
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << countOfPairs(arr, N, X);
 
    return 0;
}

Java

// Java program for the above approach
class GFG
{
 
// Function to find the number of pairs
// that satisfy the given criteria i.e.,
// i < j and (arr[i]^arr[j] )&X is 0
public static int countOfPairs(int arr[], int N, int X)
{
    // Stores the resultant count
    // of pairs
    int count = 0;
 
    // Iterate over the range [0, N)
    for (int i = 0; i < N - 1; i++) {
 
        // Iterate over the range
        for (int j = i + 1; j < N; j++) {
 
            // Check for the given
            // condition
            if (((arr[i] ^ arr[j]) & X) == 0)
                count++;
        }
    }
 
    // Return the resultant count
    return count;
}
 
// Driver Code
public static void main(String args[])
{
    int arr[] = { 3, 2, 5, 4, 6, 7 };
    int X = 6;
    int N = arr.length;
    System.out.println(countOfPairs(arr, N, X));
}
}
 
// This code is contributed by gfgking.

Python3

# Python3 program for the above approach
 
# Function to find the number of pairs
# that satisfy the given criteria i.e.,
# i < j and (arr[i]^arr[j] )&X is 0
def countOfPairs(arr, N, X):
     
    # Stores the resultant count
    # of pairs
    count = 0
 
    # Iterate over the range [0, N)
    for i in range(N - 1):
         
        # Iterate over the range
        for j in range(i + 1, N):
             
            # Check for the given
            # condition
            if (((arr[i] ^ arr[j]) & X) == 0):
                count += 1
 
    # Return the resultant count
    return count
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 3, 2, 5, 4, 6, 7 ]
    X = 6
    N = len(arr)
     
    print(countOfPairs(arr, N, X))
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the number of pairs
// that satisfy the given criteria i.e.,
// i < j and (arr[i]^arr[j] )&X is 0
static int countOfPairs(int []arr, int N, int X)
{
     
    // Stores the resultant count
    // of pairs
    int count = 0;
 
    // Iterate over the range [0, N)
    for(int i = 0; i < N - 1; i++) 
    {
         
        // Iterate over the range
        for(int j = i + 1; j < N; j++)
        {
             
            // Check for the given
            // condition
            if (((arr[i] ^ arr[j]) & X) == 0)
                count++;
        }
    }
 
    // Return the resultant count
    return count;
}
 
// Driver Code
public static void Main()
{
    int []arr = { 3, 2, 5, 4, 6, 7 };
    int X = 6;
    int N = arr.Length;
     
    Console.Write(countOfPairs(arr, N, X));
}
}
 
// This code is contributed by SURENDRA_GANGWAR

Javascript

<script>
       // JavaScript program for the above approach
 
       // Function to find the number of pairs
       // that satisfy the given criteria i.e.,
       // i < j and (arr[i]^arr[j] )&X is 0
       function countOfPairs(arr, N, X) 
       {
        
           // Stores the resultant count
           // of pairs
           let count = 0;
 
           // Iterate over the range [0, N)
           for (let i = 0; i < N - 1; i++)
           {
 
               // Iterate over the range
               for (let j = i + 1; j < N; j++) 
               {
 
                   // Check for the given
                   // condition
                   if (((arr[i] ^ arr[j]) & X) == 0)
                       count++;
               }
           }
 
           // Return the resultant count
           return count;
       }
 
       // Driver Code
       let arr = [3, 2, 5, 4, 6, 7];
       let X = 6;
       let N = arr.length;
       document.write(countOfPairs(arr, N, X));
 
   // This code is contributed by Potta Lokesh
 
   </script>

Output:

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

Efficient Approach: The above approach can also be optimized by observing the given equation. So, to perform (A[i]^A[j]) & X == 0, then unset bits in the answer of (A[i]^A[j]) at the same position where the X has set bits in its binary representation is required.

For Example, If X = 6 => 110, so to make (answer & X) == 0 where answer = A[i]^A[j], the answer should be 001 or 000. So to get the 0 bit in the answer (in the same position as the set bit the X has), it is required to have the same bit in A[i] and A[j] at that position as the Bitwise XOR of the same bit (1^1 = 0 and 0^0 = 0) gives 0.

By closely looking at the relation between X and A[i] and A[j], it is found that X&A[i] == X&A[j]. Therefore, the idea is to find the frequency of the array elements having value arr[i]&X and any two numbers with the same value can be made as a pair. Follow the steps below to solve the problem:

Initialize an unordered map, say M to store the count of numbers having a particular value arr[i]^X.
Iterate over the range [0, N] using the variable i and increase the count of the value of arr[i]&X in the unordered map M.
Initialize the variable count as 0 to store the resultant count of pairs.
Iterate over the map M using the variable m and add the value of (m.second)*(m.second – 1)/2 to the variable count.
After completing the above steps, print the value of count as the result.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number of pairs
// that satisfy the given criteria i.e.,
// i < j and (arr[i]^arr[j] )&X is 0
int countOfPairs(int arr[], int N, int X)
{
    // Stores the resultant count
    // of pairs
    int count = 0;
 
    // Initializing the map M
    unordered_map<int, int> M;
 
    // Populating the map
    for (int i = 0; i < N; i++) {
        M[(arr[i] & X)]++;
    }
 
    // Count number of pairs for every
    // element in map using mathematical
    // concept of combination
    for (auto m : M) {
        int p = m.second;
 
        // As nC2 = n*(n-1)/2
        count += p * (p - 1) / 2;
    }
 
    // Return the resultant count
    return count;
}
 
// Driver Code
int main()
{
    int arr[] = { 3, 2, 5, 4, 6, 7 };
    int X = 6;
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << countOfPairs(arr, N, X);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the number of pairs
// that satisfy the given criteria i.e.,
// i < j and (arr[i]^arr[j] )&X is 0
static int countOfPairs(int[] arr, int N, int X)
{
     
    // Stores the resultant count
    // of pairs
    int count = 0;
 
    // Initializing the map M
    HashMap<Integer, 
            Integer> M = new HashMap<Integer, 
                                     Integer>();
 
    // Populating the map
    for(int i = 0; i < N; i++) 
    {
        if (M.containsKey(arr[i] & X))
            M.put((arr[i] & X), 
             M.get(arr[i] & X) + 1);
        else
            M.put(arr[i] & X, 1);
    }
 
    // Count number of pairs for every
    // element in map using mathematical
    // concept of combination
    for(Integer entry : M.keySet())
    {
        int p = M.get(entry);
 
        // As nC2 = n*(n-1)/2
        count += p * (p - 1) / 2;
    }
 
    // Return the resultant count
    return count;
}
 
// Driver Code
public static void main(String[] args)
{
    int[] arr = { 3, 2, 5, 4, 6, 7 };
    int X = 6;
    int N = arr.length;
     
    System.out.print(countOfPairs(arr, N, X));
}
}
 
// This code is contributed by ukasp

Python3

# Python3 program for the above approach
 
# Function to find the number of pairs
# that satisfy the given criteria i.e.,
# i < j and (arr[i]^arr[j] )&X is 0
def countOfPairs(arr, N, X):
     
    # Stores the resultant count
    # of pairs
    count = 0
 
    # Initialize the dictionary M
    M = dict()
     
    # Populate the map
    for i in range(0, N):
        k = arr[i] & X
        if k in M:
            M[k] += 1
        else:
            M[k] = 1
             
    # Count number of pairs for every
    # element in map using mathematical
    # concept of combination
    for m in M.keys():
        p = M[m]
         
        # As nC2 = n*(n-1)/2
        count += p * (p - 1) // 2
         
    # Return the resultant count
    return count
 
# Driver Code
if __name__ == '__main__':
 
    arr = [ 3, 2, 5, 4, 6, 7 ]
    X = 6
    N = len(arr)
 
    print(countOfPairs(arr, N, X))
 
# This code is contributed by MuskanKalra1

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the number of pairs
// that satisfy the given criteria i.e.,
// i < j and (arr[i]^arr[j] )&X is 0
static int countOfPairs(int []arr, int N, int X)
{
   
    // Stores the resultant count
    // of pairs
    int count = 0;
 
    // Initializing the map M
    Dictionary<int,int> M = new Dictionary<int,int>();
 
    // Populating the map
    for (int i = 0; i < N; i++) {
        if(M.ContainsKey(arr[i] & X))
           M[(arr[i] & X)]++;
        else
           M.Add(arr[i] & X,1);
    }
 
    // Count number of pairs for every
    // element in map using mathematical
    // concept of combination
    foreach(KeyValuePair<int, int> entry in M)
    {
         int p = entry.Value;
 
        // As nC2 = n*(n-1)/2
        count += p * (p - 1) / 2;
    }
 
    // Return the resultant count
    return count;
}
 
// Driver Code
public static void Main()
{
    int []arr = { 3, 2, 5, 4, 6, 7 };
    int X = 6;
    int N = arr.Length;
    Console.Write(countOfPairs(arr, N, X));
}
}
 
// This code is contributed by ipg2016107.

Javascript

<script>
// Javascript program for the above approach
 
// Function to find the number of pairs
// that satisfy the given criteria i.e.,
// i < j and (arr[i]^arr[j] )&X is 0
function countOfPairs(arr, N, X) 
{
 
  // Stores the resultant count
  // of pairs
  let count = 0;
 
  // Initializing the map M
  let M = new Map();
 
  // Populating the map
  for (let i = 0; i < N; i++) {
    if (M.has(arr[i] & X)) {
      M.set(arr[i] & X, M.get(arr[i] & X) + 1);
    } else {
      M.set(arr[i] & X, 1);
    }
  }
 
  // Count number of pairs for every
  // element in map using mathematical
  // concept of combination
  for (let m of M) {
    let p = m[1];
 
    // As nC2 = n*(n-1)/2
    count += (p * (p - 1)) / 2;
  }
 
  // Return the resultant count
  return count;
}
 
// Driver Code
let arr = [3, 2, 5, 4, 6, 7];
let X = 6;
let N = arr.length;
document.write(countOfPairs(arr, N, X));
 
// This code is contributed by gfgking.
</script>

Output:

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

Reffered: https://www.geeksforgeeks.org

Arrays

Related
Minimum count of elements to be inserted in Array to form all values in [1, K] using subset sum
Sort a nearly sorted (or K sorted) array \| Set 2 (Gap method - Shell sort)
Concatenate the Array of elements into a single element
Reduce the given Array of [1, N] by rotating left or right based on given conditions
Maximize the count of adjacent element pairs with even sum by rearranging the Array

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	7