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 less than its bitwise XOR(^).
Examples:
Input: arr[] = {1, 2, 3, 4, 5}
Output: 8
Explanation:
Pairs that satisfy the given conditions are:
(1 & 2) < (1 ^ 2)
(1 & 3) < (1 ^ 3)
(1 & 4) < (1 ^ 4)
(1 & 5) < (1 ^ 5)
(2 & 4) < (2 ^ 4)
(2 & 5) < (2 ^ 5)
(3 & 4) < (3 ^ 4)
(3 & 5) < (3 ^ 5)
Therefore, the required output is 8.Input: arr[] = {1, 4, 3, 7, 10}
Output: 9
Approach: The simplest approach is to traverse the array and generate all possible pairs from the given array. For each pair, check if its bitwise AND(&) is less than the bitwise XOR(^) of that pair 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 satisfy the condition{(X & Y) > (X ^ Y)} are:
bit[i] stores the count of array elements whose position of most significant bit(MSB) is i.Therefore, total count of pairs that satisfy the given condition{(X & Y) < (X ^ Y)}
= [{N * (N – 1) /2} – {
}]
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.
- Store the position of most significant bit of each element of the given array.
- Finally, evaluate the result by the above mentioned formula and print the result.
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 condition. 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[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; } res = (N * (N - 1)) / 2 - res; return res; } // Driver Code int main() { int arr[] = { 1, 2, 3, 4, 5, 6 }; int N = sizeof (arr) / sizeof (arr[0]); cout << cntPairs(arr, N); } |
Java
// Java program to implement // the above approach import java.io.*; class GFG{ // Function to count pairs that // satisfy the above condition. static 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 ; } res = (N * (N - 1 )) / 2 - res; return res; } // Driver Code public static void main(String[] args) { int [] arr = { 1 , 2 , 3 , 4 , 5 , 6 }; int N = arr.length; System.out.println(cntPairs(arr, N)); } } // This code is contributed by akhilsaini |
Python3
# Python3 program to implement # the above approach import math # Function to count pairs that # satisfy the above condition. def 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 ( 0 , N): # Stores the index of # MSB of array elements pos = int (math.log(arr[i], 2 )) bit[pos] = bit[pos] + 1 # Calculate number of pairs for i in range ( 0 , 32 ): res = res + int ((bit[i] * (bit[i] - 1 )) / 2 ) res = int ((N * (N - 1 )) / 2 - res) return res # Driver Code if __name__ = = "__main__" : arr = [ 1 , 2 , 3 , 4 , 5 , 6 ] N = len (arr) print (cntPairs(arr, N)) # This code is contributed by akhilsaini |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to count pairs that // satisfy the above condition. static 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; } res = (N * (N - 1)) / 2 - res; return res; } // Driver Code public static void Main() { int [] arr = { 1, 2, 3, 4, 5, 6 }; int N = arr.Length; Console.Write(cntPairs(arr, N)); } } // This code is contributed by akhilsaini |
Javascript
<script> // Javascript program to implement // the above approach // Function to count pairs that // satisfy the above condition. function cntPairs(arr, N) { // Stores the count // of pairs let res = 0; // Stores the count of array // elements having same // positions of MSB let bit = new Array(32).fill(0); // Traverse the array for (let i = 0; i < N; i++) { // Stores the index of // MSB of array elements let pos = parseInt(Math.log(arr[i]) / Math.log(2));; bit[pos]++; } // Calculate number of pairs for (let i = 0; i < 32; i++) { res += parseInt((bit[i] * (bit[i] - 1)) / 2); } res = parseInt((N * (N - 1)) / 2) - res; return res; } // Driver Code let arr = [ 1, 2, 3, 4, 5, 6 ]; let N = arr.length; document.write(cntPairs(arr, N)); // This code is contributed by subhammahato348. </script> |
11
Time Complexity: O(N)
Auxiliary Space: O(1)
Method 2 : Bitwise and is greater than bitwise xor if and only if most significant bit is equal.
- Create a bits[] array of size 32 (max no of bits)
- Initialize ans to 0.
- We will traverse the array from the start and for each number,
- Find its most significant bit and say it is j.
- Add the value stored in bits[j] array to the ans. (for the current element bits[j] number of pairs can be formed)
- Now increase the value of bits[j] by 1.
- Now total number of pairs = n*(n-1)/2. Subtract the ans from it.
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; int findCount( int arr[], int N) { // For storing number of pairs int ans = 0; // For storing count of numbers int bits[32] = { 0 }; // Iterate from 0 to N - 1 for ( int i = 0; i < N; i++) { // Find the most significant bit int val = log2l(arr[i]); ans += bits[val]; bits[val]++; } return N * (N - 1) / 2 - ans; } // Driver Code int main() { // Given array arr[] int arr[] = { 1, 2, 3, 4, 5, 6 }; int N = sizeof (arr) / sizeof (arr[0]); // Function Call cout << findCount(arr, N); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG{ static int findCount( int arr[], int N) { // For storing number of pairs int ans = 0 ; // For storing count of numbers int bits[] = new int [ 32 ]; // Iterate from 0 to N - 1 for ( int i = 0 ; i < N; i++) { // Find the most significant bit int val = ( int )(Math.log(arr[i]) / Math.log( 2 )); ans += bits[val]; bits[val]++; } return N * (N - 1 ) / 2 - ans; } // Driver Code public static void main(String[] args) { // Given array arr[] int arr[] = { 1 , 2 , 3 , 4 , 5 , 6 }; int N = arr.length; // Function Call System.out.println(findCount(arr, N)); } } // This code is contributed by Kingash |
Python3
# Python3 program for the above approach import math def findCount(arr, N): # For storing number of pairs ans = 0 # For storing count of numbers bits = [ 0 ] * 32 # Iterate from 0 to N - 1 for i in range (N): # Find the most significant bit val = int (math.log2(arr[i])) ans + = bits[val] bits[val] + = 1 return (N * (N - 1 ) / / 2 - ans) # Driver Code if __name__ = = "__main__" : # Given array arr[] arr = [ 1 , 2 , 3 , 4 , 5 , 6 ] N = len (arr) # Function Call print (findCount(arr, N)) # This code is contributed by ukasp. |
C#
// C# program for the above approach using System; class GFG{ static int findCount( int [] arr, int N) { // For storing number of pairs int ans = 0; // For storing count of numbers int [] bits = new int [32]; // Iterate from 0 to N - 1 for ( int i = 0; i < N; i++) { // Find the most significant bit int val = ( int )(Math.Log(arr[i]) / Math.Log(2)); ans += bits[val]; bits[val]++; } return N * (N - 1) / 2 - ans; } // Driver Code public static void Main() { // Given array arr[] int [] arr = { 1, 2, 3, 4, 5, 6 }; int N = arr.Length; // Function Call Console.Write(findCount(arr, N)); } } // This code is contributed by subhammahato348 |
Javascript
<script> // Javascript program for the above approach function findCount(arr, N) { // For storing number of pairs let ans = 0; // For storing count of numbers let bits = new Array(32).fill(0); // Iterate from 0 to N - 1 for (let i = 0; i < N; i++) { // Find the most significant bit let val = parseInt(Math.log(arr[i]) / Math.log(2)); ans += bits[val]; bits[val]++; } return parseInt(N * (N - 1) / 2) - ans; } // Driver Code // Given array arr[] let arr = [ 1, 2, 3, 4, 5, 6 ]; let N = arr.length; // Function Call document.write(findCount(arr, N)); // This code is contributed by subhammahato348 </script> |
11
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!