Given an array arr that contains N positive Integers. Find the count of all possible pairs whose bitwise XOR value is greater than bitwise AND value
Examples:
Input : arr[]={ 12, 4, 15}
Output: 2
Explanation: 12 ^ 4 = 8, 12 & 4 = 4. so 12 ^ 4 > 12 & 4
4 ^ 15 = 11, 4 & 15 = 4. so 4 ^ 15 > 4 & 15 .
So, above two are valid pairs { 12, 4 }, {4, 15} .Input: arr[] = { 1, 1, 3, 3 }
Output: 4
Approach: Refer to the below idea for the approach to solve this problem:
We know that, for an array of length N, there will be a total (N*(N-1))/2 pairs.
Therefore check for every pair, and increase count by one if a pair satisfy the given condition in the question.
Follow the below steps to solve this problem:
- Check for every pair whether their bit wise XOR value is greater than bit wise AND or not.
- If yes then increase the count
- Return the count.
Below is the Implementation of the above approach:
C++
// C++ program to Count number of pairs// whose bit wise XOR value is greater// than bit wise AND value#include <bits/stdc++.h>using namespace std;// Function that return count of pairs// whose bitwise xor >= bitwise andlong long valid_pairs(int arr[], int N){ long long cnt = 0; // check for all possible pairs for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { if ((arr[i] ^ arr[j]) >= (arr[i] & arr[j])) cnt++; } } return cnt;}// Driver Codeint main(){ int N = 3; int arr[] = { 12, 4, 15 }; cout << valid_pairs(arr, N);} |
Java
// Java program to Count number of pairs// whose bit wise XOR value is greater// than bit wise AND valueimport java.io.*;class GFG { // Function that return count of pairs // whose bitwise xor >= bitwise public static long valid_pairs(int arr[], int N) { long cnt = 0; // check for all possible pairs for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { if ((arr[i] ^ arr[j]) >= (arr[i] & arr[j])) cnt++; } } return cnt; } // Driver code public static void main(String[] args) { int N = 3; int arr[] = { 12, 4, 15 }; System.out.print(valid_pairs(arr, N)); }}// This code is contributed by Rohit Pradhan. |
Python3
# python3 program to Count number of pairs# whose bit wise XOR value is greater# than bit wise AND value# Function that return count of pairs# whose bitwise xor >= bitwisedef valid_pairs(arr, N): cnt = 0 # check for all possible pairs for i in range(0, N): for j in range(i + 1, N): if ((arr[i] ^ arr[j]) >= (arr[i] & arr[j])): cnt += 1 return cnt# Driver Codeif __name__ == "__main__": N = 3 arr = [12, 4, 15] print(valid_pairs(arr, N)) # This code is contributed by rakeshsahni |
C#
// C# program to Count number of pairs// whose bit wise XOR value is greater// than bit wise AND valueusing System;class GFG { // Function that return count of pairs // whose bitwise xor >= bitwise public static long valid_pairs(int[] arr, int N) { long cnt = 0; // check for all possible pairs for (int i = 0; i < N; i++) { for (int j = i + 1; j < N; j++) { if ((arr[i] ^ arr[j]) >= (arr[i] & arr[j])) cnt++; } } return cnt; } // Driver code public static void Main(string[] args) { int N = 3; int[] arr = { 12, 4, 15 }; Console.Write(valid_pairs(arr, N)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach // Function that return count of pairs // whose bitwise xor >= bitwise function valid_pairs(arr, N) { let cnt = 0; // check for all possible pairs for (let i = 0; i < N; i++) { for (let j = i + 1; j < N; j++) { if ((arr[i] ^ arr[j]) >= (arr[i] & arr[j])) cnt++; } } return cnt; } // Driver Code let N = 3; let arr = [12, 4, 15]; document.write(valid_pairs(arr, N)); // This code is contributed by Potta Lokesh </script> |
2
Time Complexity: O(N*N)
Auxiliary Space: O(1)
