Count pairs with Bitwise XOR greater than both the elements of the pair
Given an array arr[] of size N, the task is to count the number of pairs whose Bitwise XOR is greater than both the elements in the pair.
Examples:
Input: arr[] = {2, 4, 3}
Output: 2
Explanation: There are only 2 pairs whose Bitwise XOR is greater than both the elements in the pair:
1) (2, 4): Bitwise XOR = 2 ^ 4 = 6, which is greater than both 2 and 4.
2) (4, 3): Bitwise XOR = 4 ^ 3 = 7, which is greater than both 4 and 3.Input: arr[] = {2, 2, 2}
Output: 0
Explanation:Since all array elements are the same, Bitwise XOR of all possible pairs is 0. Therefore, no such pair exists
Approach: The simplest approach is to generate all possible pairs from the given array and count those pairs whose Bitwise XOR is greater than both the elements. Print the count after checking all the pairs only once.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function that counts the pairs whose // Bitwise XOR is greater than both // the elements of pair void countPairs( int A[], int N) { // Stores the count of pairs int count = 0; // Generate all possible pairs for ( int i = 0; i < N; i++) { for ( int j = i + 1; j < N; j++) { // Find the Bitwise XOR int xo = (A[i] ^ A[j]); // Find the maximum of two int mx = max(A[i], A[j]); // If xo < mx, increment count if (xo > mx) { count++; } } } // Print the value of count cout << count; } // Driver Code int main() { int arr[] = { 2, 4, 3 }; int N = sizeof (arr) / sizeof (arr[0]); // Function Call countPairs(arr, N); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG{ // Function that counts the pairs whose // Bitwise XOR is greater than both // the elements of pair static void countPairs( int [] A, int N) { // Stores the count of pairs int count = 0 ; // Generate all possible pairs for ( int i = 0 ; i < N; i++) { for ( int j = i + 1 ; j < N; j++) { // Find the Bitwise XOR int xo = (A[i] ^ A[j]); // Find the maximum of two int mx = Math.max(A[i], A[j]); // If xo < mx, increment count if (xo > mx) { count++; } } } // Print the value of count System.out.println(count); } // Driver Code public static void main(String[] args) { int [] arr = { 2 , 4 , 3 }; int N = arr.length; // Function Call countPairs(arr, N); } } // This code is contributed by akhilsaini |
Python3
# Python3 program for the above approach # Function that counts the pairs whose # Bitwise XOR is greater than both # the elements of pair def countPairs(A, N): # Stores the count of pairs count = 0 # Generate all possible pairs for i in range ( 0 , N): for j in range (i + 1 , N): # Find the Bitwise XOR xo = (A[i] ^ A[j]) # Find the maximum of two mx = max (A[i], A[j]) # If xo < mx, increment count if (xo > mx): count + = 1 # Print the value of count print (count) # Driver Code if __name__ = = '__main__' : arr = [ 2 , 4 , 3 ] N = len (arr) # Function Call countPairs(arr, N) # This code is contributed by akhilsaini |
C#
// C# program for the above approach using System; class GFG{ // Function that counts the pairs whose // Bitwise XOR is greater than both // the elements of pair static void countPairs( int [] A, int N) { // Stores the count of pairs int count = 0; // Generate all possible pairs for ( int i = 0; i < N; i++) { for ( int j = i + 1; j < N; j++) { // Find the Bitwise XOR int xo = (A[i] ^ A[j]); // Find the maximum of two int mx = Math.Max(A[i], A[j]); // If xo < mx, increment count if (xo > mx) { count++; } } } // Print the value of count Console.WriteLine(count); } // Driver Code public static void Main() { int [] arr = { 2, 4, 3 }; int N = arr.Length; // Function Call countPairs(arr, N); } } // This code is contributed by akhilsaini |
Javascript
<script> // javascript program for the above approach // Function that counts the pairs whose // Bitwise XOR is greater than both // the elements of pair function countPairs(A , N) { // Stores the count of pairs var count = 0; // Generate all possible pairs for (i = 0; i < N; i++) { for (j = i + 1; j < N; j++) { // Find the Bitwise XOR var xo = (A[i] ^ A[j]); // Find the maximum of two var mx = Math.max(A[i], A[j]); // If xo < mx, increment count if (xo > mx) { count++; } } } // Print the value of count document.write(count); } // Driver Code var arr = [ 2, 4, 3 ]; var N = arr.length; // Function Call countPairs(arr, N); // This code contributed by Rajput-Ji </script> |
2
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use Bit Manipulation. Consider X = A^B and A < B and Let K be the Most Significant Bit of the number A. Now, If X is greater than both the element A and B if and only if the Kth bit of B is 0. If the Kth bit of an integer is already 0, then count the numbers such that the Kth bit is the MSB bit of the other integer. Below are the steps:
- Initialize a variable count to store the count of pairs and an array say bits[] of size 32 and sort the given array.
- Traverse the array and do the following:
- If the current element is 0 then check for the next element.
- Else traverse all the bits of the current element and if any bit at position j is set then increment the count by bits[j].
- After the above steps, Update the bits[log2(current element)] by 1.
- After the above steps, print the value of the 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 count pairs whose XOR // is greater than the pair itself void countPairs( int A[], int N) { // Stores the count of pairs int count = 0; // Sort the array sort(A, A + N); int bits[32] = { 0 }; // Traverse the array for ( int i = 0; i < N; i++) { // If current element is 0, // then ignore it if (A[i] == 0) { continue ; } // Traverse all the bits of // element A[i] for ( int j = 0; j < 32; j++) { // If current bit is set // then update the count if (!((1LL << j) & A[i])) { count += bits[j]; } } // Update bits[] at the most // significant bit of A[i] ++bits[( int )(log2l(A[i]))]; } // Print the count cout << count; } // Driver Code int main() { int arr[] = { 2, 4, 3 }; int N = sizeof (arr) / sizeof (arr[0]); // Function Call countPairs(arr, N); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG{ // Function to count pairs whose XOR // is greater than the pair itself static void countPairs( int [] A, int N) { // Stores the count of pairs int count = 0 ; // Sort the array Arrays.sort(A); int [] bits = new int [ 32 ]; // Traverse the array for ( int i = 0 ; i < N; i++) { // If current element is 0, // then ignore it if (A[i] == 0 ) { continue ; } // Traverse all the bits of // element A[i] for ( int j = 0 ; j < 32 ; j++) { // If current bit is set // then update the count if ((( 1 << j) & A[i]) == 0 ) { count += bits[j]; } } // Update bits[] at the most // significant bit of A[i] ++bits[( int )(( int )(Math.log(A[i]) / Math.log( 2 )))]; } // Print the count System.out.println(count); } // Driver Code public static void main(String[] args) { int [] arr = { 2 , 4 , 3 }; int N = arr.length; // Function Call countPairs(arr, N); } } // This code is contributed by akhilsaini |
Python3
# Python3 program for the above approach import math # Function to count pairs whose XOR # is greater than the pair itself def countPairs(A, N): # Stores the count of pairs count = 0 # Sort the array A.sort() bits = [ 0 ] * 32 # Traverse the array for i in range ( 0 , N): # If current element is 0, # then ignore it if (A[i] = = 0 ): continue # Traverse all the bits of # element A[i] for j in range ( 0 , 32 ): # If current bit is set # then update the count if ((( 1 << j) & A[i]) = = 0 ): count + = bits[j] # Update bits[] at the most # significant bit of A[i] bits[( int )(math.log(A[i], 2 ))] + = 1 # Print the count print (count) # Driver Code if __name__ = = '__main__' : arr = [ 2 , 4 , 3 ] N = len (arr) # Function Call countPairs(arr, N) # This code is contributed by akhilsaini |
C#
// C# program for the above approach using System; class GFG{ // Function to count pairs whose XOR // is greater than the pair itself static void countPairs( int [] A, int N) { // Stores the count of pairs int count = 0; // Sort the array Array.Sort(A); int [] bits = new int [32]; // Traverse the array for ( int i = 0; i < N; i++) { // If current element is 0, // then ignore it if (A[i] == 0) { continue ; } // Traverse all the bits of // element A[i] for ( int j = 0; j < 32; j++) { // If current bit is set // then update the count if (((1 << j) & A[i]) == 0) { count += bits[j]; } } // Update bits[] at the most // significant bit of A[i] ++bits[( int )(( int )(Math.Log(A[i]) / Math.Log(2)))]; } // Print the count Console.WriteLine(count); } // Driver Code public static void Main() { int [] arr = { 2, 4, 3 }; int N = arr.Length; // Function Call countPairs(arr, N); } } // This code is contributed by akhilsaini |
Javascript
<script> // javascript program for the above approach // Function to count pairs whose XOR // is greater than the pair itself function countPairs(A , N) { // Stores the count of pairs var count = 0; // Sort the array A.sort(); var bits = Array(32).fill(0); // Traverse the array for (i = 0; i < N; i++) { // If current element is 0, // then ignore it if (A[i] == 0) { continue ; } // Traverse all the bits of // element A[i] for (j = 0; j < 32; j++) { // If current bit is set // then update the count if (((1 << j) & A[i]) == 0) { count += bits[j]; } } // Update bits at the most // significant bit of A[i] bits[parseInt(Math.log(A[i]) / Math.log(2))]++; } // Print the count document.write(count); } // Driver Code var arr = [ 2, 4, 3 ]; var N = arr.length; // Function Call countPairs(arr, N); // This code is contributed by Rajput-Ji. </script> |
2
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Contact Us