Given an array A[] consisting of N integers, the task is to count the number of pairs (i, j) such that i < j, and Bitwise OR of A[i] and A[j] is greater than Bitwise AND of A[i] and A[j].
Examples:
Input: A[] = {1, 4, 7}
Output: 3
Explanation:
There are 3 such pairs: (1, 4), (4, 7), (1, 7).
1) 1 | 4 (= 5) > 1 & 4 (= 0)
2) 4 | 7 (= 7) > 4 & 7 (= 4)
3) 1 | 7 (= 7) > 1 & 7 (= 1)Input: A[] = {3, 3, 3}
Output: 0
Explanation: There exist no such pair.
Naive Approach: The simplest approach is to generate all possible pairs from the given array and for every pair (i, j), if it satisfies the given conditions, then increment the count by 1. After checking for all the pairs, 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 count the number of// pairs (i, j) their Bitwise OR is// greater than Bitwise ANDvoid countPairs(int A[], int n){ // Store the required answer int count = 0; // Check for all possible pairs for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) // If the condition satisfy // then increment count by 1 if ((A[i] | A[j]) > (A[i] & A[j])) { count++; } } // Print the answer cout << count;}// Driver Codeint main(){ int A[] = { 1, 4, 7 }; int N = sizeof(A) / sizeof(A[0]); // Function Call countPairs(A, N); return 0;} |
Java
// Java program to implement // the above approach import java.util.*;class GFG{ // Function to count the number of // pairs (i, j) their Bitwise OR is // greater than Bitwise AND static void countPairs(int A[], int n) { // Store the required answer int count = 0; // Check for all possible pairs for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) // If the condition satisfy // then increment count by 1 if ((A[i] | A[j]) > (A[i] & A[j])) { count++; } } // Print the answer System.out.println(count); } // Driver Code public static void main(String args[]) { int A[] = { 1, 4, 7 }; int N = A.length; // Function Call countPairs(A, N); }}// This code is contributed by splevel62. |
Python3
# Python program to implement# the above approach# Function to count the number of# pairs (i, j) their Bitwise OR is# greater than Bitwise ANDdef countPairs(A, n): # Store the required answer count = 0; # Check for all possible pairs for i in range(n): for j in range(i + 1, n): # If the condition satisfy # then increment count by 1 if ((A[i] | A[j]) > (A[i] & A[j])): count += 1; # Print the answer print(count);# Driver Codeif __name__ == '__main__': A = [1, 4, 7]; N = len(A); # Function Call countPairs(A, N); # This code is contributed by 29AjayKumar |
C#
// C# program to implement// the above approachusing System;class GFG { // Function to count the number of // pairs (i, j) their Bitwise OR is // greater than Bitwise AND static void countPairs(int[] A, int n) { // Store the required answer int count = 0; // Check for all possible pairs for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) // If the condition satisfy // then increment count by 1 if ((A[i] | A[j]) > (A[i] & A[j])) { count++; } } // Print the answer Console.Write(count);}// Driver Codepublic static void Main(){ int[] A = { 1, 4, 7 }; int N = A.Length; // Function Call countPairs(A, N);}}// This code is contributed by susmitakundugoaldanga. |
Javascript
<script>// Javascript program for the above approach// Function to count the number of// pairs (i, j) their Bitwise OR is// greater than Bitwise ANDfunction countPairs( A, n){ // Store the required answer var count = 0; // Check for all possible pairs for (var i = 0; i < n; i++) { for (var j = i + 1; j < n; j++) // If the condition satisfy // then increment count by 1 if ((A[i] | A[j]) > (A[i] & A[j])) { count++; } } // Print the answer document.write( count);}// Driver Codevar A = [ 1, 4, 7 ];var N = A.length;// Function CallcountPairs(A, N);</script> |
Output:
3
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is based on the observation that the condition Ai | Aj > Ai & Aj is satisfied only when Ai and Aj are distinct. If Ai is equal to Aj, then Ai | Aj = Ai & Aj. The condition Ai | Aj < Ai & Aj is never met. Hence, the problem can be solved by subtracting the number of pairs having an equal value from the total number of pairs possible. Follow the steps below to solve the problem:
- Initialize a variable, say count, with N * (N – 1) / 2 that denotes the total number of possible pairs.
- Initialize a hashmap, say M to store the frequency of each array element.
- Traverse the array arr[] and for each array element arr[i], increment the frequency of arr[i] in M by 1.
- Now, traverse the hashmap M and for each key K, and its corresponding value X, subtract the value of (X * (X – 1))/2 from the 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 count the number of// pairs (i, j) their Bitwise OR is// greater than Bitwise ANDvoid countPairs(int A[], int n){ // Total number of pairs // possible from the array long long count = (n * (n - 1)) / 2; // Stores frequency of each array element unordered_map<long long, long long> ump; // Traverse the array A[] for (int i = 0; i < n; i++) { // Increment ump[A[i]] by 1 ump[A[i]]++; } // Traverse the Hashmap ump for (auto it = ump.begin(); it != ump.end(); ++it) { // Subtract those pairs (i, j) // from count which has the // same element on index i // and j (i < j) long long c = it->second; count = count - (c * (c - 1)) / 2; } // Print the result cout << count;}// Driver Codeint main(){ int A[] = { 1, 4, 7 }; int N = sizeof(A) / sizeof(A[0]); // Function Call countPairs(A, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to count the number of// pairs (i, j) their Bitwise OR is// greater than Bitwise ANDstatic void countPairs(int A[], int n){ // Total number of pairs // possible from the array int count = (n * (n - 1)) / 2; // Stores frequency of each array element Map<Integer,Integer> mp = new HashMap<>(); // Traverse the array A[] for (int i = 0 ; i < n; i++){ if(mp.containsKey(A[i])){ mp.put(A[i], mp.get(A[i])+1); } else{ mp.put(A[i], 1); } } // Traverse the Hashmap ump for (Map.Entry<Integer,Integer> it : mp.entrySet()){ // Subtract those pairs (i, j) // from count which has the // same element on index i // and j (i < j) int c = it.getValue(); count = count - (c * (c - 1)) / 2; } // Print the result System.out.print(count);}// Driver Codepublic static void main(String[] args){ int A[] = { 1, 4, 7 }; int N = A.length; // Function Call countPairs(A, N);}}// This code is contributed by shikhasingrajput |
Python3
# Python 3 program for the above approachfrom collections import defaultdict# Function to count the number of# pairs (i, j) their Bitwise OR is# greater than Bitwise ANDdef countPairs(A, n): # Total number of pairs # possible from the array count = (n * (n - 1)) // 2 # Stores frequency of each array element ump = defaultdict(int) # Traverse the array A[] for i in range(n): # Increment ump[A[i]] by 1 ump[A[i]] += 1 # Traverse the Hashmap ump for it in ump.keys(): # Subtract those pairs (i, j) # from count which has the # same element on index i # and j (i < j) c = ump[it] count = count - (c * (c - 1)) // 2 # Print the result print(count)# Driver Codeif __name__ == "__main__": A = [1, 4, 7] N = len(A) # Function Call countPairs(A, N) # This code is contributed by chitranayal. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG { // Function to count the number of // pairs (i, j) their Bitwise OR is // greater than Bitwise AND static void countPairs(int[] A, int n) { // Total number of pairs // possible from the array long count = (n * (n - 1)) / 2; // Stores frequency of each array element Dictionary<long, long> ump = new Dictionary<long, long>(); // Traverse the array A[] for (int i = 0; i < n; i++) { // Increment ump[A[i]] by 1 if(ump.ContainsKey(A[i])) { ump[A[i]]++; } else{ ump[A[i]] = 1; } } // Traverse the Hashmap ump foreach(KeyValuePair<long, long> it in ump) { // Subtract those pairs (i, j) // from count which has the // same element on index i // and j (i < j) long c = it.Value; count = count - (c * (c - 1)) / 2; } // Print the result Console.WriteLine(count); } // Driver code static void Main() { int[] A = { 1, 4, 7 }; int N = A.Length; // Function Call countPairs(A, N); }}// This code is contributed by divyeshrabadiya07. |
Javascript
<script>// Javascript program for the above approach // Function to count the number of // pairs (i, j) their Bitwise OR is // greater than Bitwise AND function countPairs(A, n) { // Total number of pairs // possible from the array var count = (n * (n - 1)) / 2; // Stores frequency of each array element var ump = new Map(); // Traverse the array A[] for (var i = 0; i < n; i++) { // Increment ump[A[i]] by 1 if(ump.has(A[i])) { ump.set(A[i], ump.get(A[i])+1); } else{ ump.set(A[i], 1); } } // Traverse the Hashmap ump for(var it of ump) { // Subtract those pairs (i, j) // from count which has the // same element on index i // and j (i < j) var c = it[1]; count = count - (c * (c - 1)) / 2; } // Print the result document.write(count + "<br>"); } // Driver code var A = [1, 4, 7]; var N = A.length; // Function Call countPairs(A, N);// This code is contributed by rutvik_56.</script> |
Output:
3
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
