Given an array arr[] of size N, the task is to count the number of pairs from the given array such that the Bitwise AND (&) of each pair is greater than its Bitwise XOR(^).
Examples :
Input: arr[] = {1, 2, 3, 4}
Output:1
Explanation:
Pairs that satisfy the given conditions are:
(2 & 3) > (2 ^ 3)
Therefore, the required output is 1.Input: arr[] = {1, 4, 3, 7}
Output: 1
Explanation:
Pairs that satisfy the given conditions are:
(4 & 7) > (4 ^ 7)
Therefore, the required output is 1.
Naive Approach: The simplest approach to solve the problem is to traverse the array and generate all possible pairs from the given array. For each pair, check if its Bitwise AND( & ) is greater than its Bitwise XOR( ^ ) or not. If found to be true, then increment the count of pairs by 1. Finally, print the count of such pairs obtained.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient approach: To optimize the above approach, follow the properties of the Bitwise Operators:
1 ^ 0 = 1
0 ^ 1 = 1
1 & 1 = 1
X = b31b30…..b1b0
Y = a31b30….a1a0
If the expression {(X & Y) > (X ^ Y)} is true, then the Most Significant Bit (MSB) of both X and Y must be equal.
Total count of pairs that satisfying the condition {(X & Y) > (X ^ Y)} is equal to:
![\Sigma_{n=0}^{31}(^{bit[i]}_{\ \ \ 2})](https://neveropen.co.uk/wp-content/uploads/2023/11/dominic_rubhabha_quicklatex.com-48456ce928496385bcaf23467a24f650_l3.png "Rendered by QuickLaTeX.com")
Follow the steps below to solve the problem:
- Initialize a variable, say res, to store the count of pairs that satisfy the given condition.
- Traverse the given array arr[].
- Store the positions of the Most Significant Bit (MSB) of each element of the given array.
- Initialize an array bits[], of size 32 (max no of bits)
- Iterate over each array element and perform the following steps:
- Find the Most Significant Bit (MSB) of the current array element, say j.
- Add the value stored in bits[j] to the answer.
- Increase the value of bits[j] by 1.
Below is the implementation of the above approach
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to count pairs that// satisfy the above conditionint cntPairs(int arr[], int N){ // Stores the count of pairs int res = 0; // Stores the count of array // elements having same // positions of MSB int bit[32] = { 0 }; // Traverse the array for (int i = 0; i < N; i++) { // Stores the index of // MSB of array elements int pos = log2(arr[i]); bit[pos]++; } // Calculate number of pairs for (int i = 0; i < 32; i++) { res += (bit[i] * (bit[i] - 1)) / 2; } return res;}// Driver Codeint main(){ // Given Input int arr[] = { 1, 2, 3, 4 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call to count pairs // satisfying the given condition cout << cntPairs(arr, N);} |
Java
// Java program to implement// the above approachimport java.io.*;class GFG{// Function to count pairs that// satisfy the above conditionstatic int cntPairs(int arr[], int N){ // Stores the count of pairs int res = 0; // Stores the count of array // elements having same // positions of MSB int bit[] = new int[32]; // Traverse the array for(int i = 0; i < N; i++) { // Stores the index of // MSB of array elements int pos = (int)(Math.log(arr[i]) / Math.log(2)); bit[pos]++; } // Calculate number of pairs for(int i = 0; i < 32; i++) { res += (bit[i] * (bit[i] - 1)) / 2; } return res;}// Driver Codepublic static void main(String[] args){ // Given Input int arr[] = { 1, 2, 3, 4 }; int N = arr.length; // Function call to count pairs // satisfying the given condition System.out.println(cntPairs(arr, N));}}// This code is contributed by Dharanendra L V. |
Python3
# Python3 program to implement# the above approachimport math# Function to count pairs that# satisfy the above conditiondef cntPairs(arr, N): # Stores the count of pairs res = 0 # Stores the count of array # elements having same # positions of MSB bit = [0] * 32 # Traverse the array for i in range(N): # Stores the index of # MSB of array elements pos = (int)(math.log2(arr[i])) bit[pos] += 1 # Calculate number of pairs for i in range(32): res += (bit[i] * (bit[i] - 1)) // 2 return res# Driver Codeif __name__ == "__main__": # Given Input arr = [1, 2, 3, 4] N = len(arr) # Function call to count pairs # satisfying the given condition print(cntPairs(arr, N))# This code is contributed by ukasp |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to count pairs that// satisfy the above conditionstatic int cntPairs(int[] arr, int N){ // Stores the count of pairs int res = 0; // Stores the count of array // elements having same // positions of MSB int[] bit = new int[32]; // Traverse the array for(int i = 0; i < N; i++) { // Stores the index of // MSB of array elements int pos = (int)(Math.Log(arr[i]) / Math.Log(2)); bit[pos]++; } // Calculate number of pairs for(int i = 0; i < 32; i++) { res += (bit[i] * (bit[i] - 1)) / 2; } return res;}// Driver Codestatic public void Main (){ // Given Input int[] arr = { 1, 2, 3, 4 }; int N = arr.Length; // Function call to count pairs // satisfying the given condition Console.Write(cntPairs(arr, N));}}// This code is contributed by avijitmondal1998 |
Javascript
<script>// Javascript program to implement// the above approach// Function to count pairs that// satisfy the above conditionfunction cntPairs(arr, N){ // Stores the count of pairs var res = 0; // Stores the count of array // elements having same // positions of MSB var bit = Array(32).fill(0); var i; // Traverse the array for( i = 0; i < N; i++) { // Stores the index of // MSB of array elements var pos = Math.ceil(Math.log2(arr[i])); bit[pos] += 1; } // Calculate number of pairs for (i = 0; i < 32; i++) { res += Math.ceil((bit[i] * (bit[i] - 1)) / 2); } return res;}// Driver Code // Given Input arr = [1, 2, 3, 4]; N = arr.length; // Function call to count pairs // satisfying the given condition document.write(cntPairs(arr, N));</script> |
1
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
