Given an array arr[] of size N and an integer K, the task is to find the count of all the ordered pairs (i, j) where i != j, such that ((arr[i] ⊕ arr[j]) & K) = 0. The ⊕ represents bitwise XOR and & represents bitwise AND.
Examples:
Input: arr = [1, 2, 3, 4, 5], K = 3
Output: 2
Explanation: There are 2 pairs satisfying the condition.
These pairs are: (1, 5) and (5, 1)Input: arr = [5, 9, 24], K = 7
Output: 0
Explanation: No such pair satisfying the condition exists.
Approach: The given problem can be solved with the help of the following idea:
Using distributive property, we can write ((arr[i] ⊕ arr[j]) & K) = ((arr[i] & K) ⊕ (arr[j] & K)).
Since for ((arr[i] & K) ⊕ (arr[j] & K)) = 0, these two terms (arr[i] & K) and (arr[j] & K) must be equal.
Follow the below steps to solve the problem:
- Create a map and an answer variable (say Res = 0).
- Traverse the array and insert (arr[i] & K) to map with its count.
- Now, traverse the map and for each entry if there are X such occurrences then possible pairs = X*(X-1). So add that to the value Res.
- Return Res as the required answer.
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach #include <bits/stdc++.h> using namespace std; // Function to find pair satisfying the condition int findPair( int * arr, int N, int K) { map< int , int > Mp; int Res = 0; for ( int i = 0; i < N; i++) Mp[arr[i] & K]++; for ( auto i : Mp) Res += ((i.second - 1) * i.second); return Res; } // Driver Code int main() { int arr[] = { 1, 2, 3, 4, 5 }; int N = sizeof (arr) / sizeof (arr[0]); int K = 3; // Function call cout << findPair(arr, N, K) << endl; return 0; } |
Java
// Java code to implement the above approach import java.util.*; class GFG { // Function to find pair satisfying the condition static int findPair( int arr[], int N, int K) { Map<Integer, Integer> mp = new HashMap<>(); int Res = 0 ; for ( int i = 0 ; i < N; i++) { if (mp.containsKey((arr[i] & K))) { mp.put((arr[i] & K), mp.get((arr[i] & K)) + 1 ); } else { mp.put((arr[i] & K), 1 ); } } for (Map.Entry<Integer, Integer> i : mp.entrySet()) { Res += ((i.getValue() - 1 ) * i.getValue()); } return Res; } // Driver Code public static void main (String[] args) { int arr[] = { 1 , 2 , 3 , 4 , 5 }; int N = arr.length; int K = 3 ; // Function call System.out.println(findPair(arr, N, K)); } } // This code is contributed by hrithikgarg03188. |
Python3
# Python3 code to implement the above approach # Function to find pair satisfying the condition def findPair(arr, N, K) : Mp = {}; Res = 0 ; for i in range (N) : Mp[arr[i] & K] = Mp.get(arr[i] & K, 0 ) + 1 ; for i in Mp: Res + = ((Mp[i] - 1 ) * Mp[i]); return Res; # Driver Code if __name__ = = "__main__" : arr = [ 1 , 2 , 3 , 4 , 5 ]; N = len (arr); K = 3 ; # Function call print (findPair(arr, N, K)); # This code is contributed by AnkThon |
C#
using System; using System.Collections.Generic; public class GFG{ // Function to find pair satisfying the condition public static int findPair( int [] arr, int N, int K) { SortedDictionary< int , int >Mp= new SortedDictionary< int , int >(); int Res = 0; // Initialising Mp with 0 for ( int i=0;i<N;i++) { Mp[i] = 0; } for ( int i = 0; i < N; i++) Mp[(arr[i] & K)]++; foreach ( KeyValuePair< int , int > kvp in Mp ) { Res+=(( kvp.Value - 1) * kvp.Value); } return Res; } static public void Main (){ int [] arr = { 1, 2, 3, 4, 5 }; int N =arr.Length; int K = 3; // Function call Console.WriteLine( findPair(arr, N, K) ); } } // This code is contributed by akashish__ |
Javascript
<script> // JavaScript code for the above approach // Function to find pair satisfying the condition function findPair(arr, N, K) { let Mp = new Map(); let Res = 0; for (let i = 0; i < N; i++) { Mp[arr[i] & K]++; if (Mp.has(arr[i] & K)) { Mp.set(arr[i] & K, Mp.get(arr[i] & K) + 1) } else { Mp.set(arr[i] & K, 1); } } for (let [key, val] of Mp) Res += ((val - 1) * val); return Res; } // Driver Code let arr = [1, 2, 3, 4, 5]; let N = arr.length; let K = 3; // Function call document.write(findPair(arr, N, K) + '<br>' ); // This code is contributed by Potta Lokesh </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!