Count Number of Pairs where Bitwise AND and Bitwise XOR is Equal
Given an integer array arr of size N, the task is to count the number of pairs whose BITWISE AND and BITWISE XOR are equal.
Example:
Input: N = 3, arr[] = {0,0,1}
Output: 1
Explanation: There is only one pair arr[0] and arr[1] as 0&0=0 and 0^0=0Input: N = 4, arr[] = {1, 2, 4, 8}
Output: 0
Explanation: There are no pairs satisfying the condition.
Approach: This can be solved with the following idea:
To make Bitwise XOR and Bitwise AND equal, it is only possible when both bits of first and second element are 0 at each bit place. Therefore, it boils down to calculate number of pairs possible where both elements are 0.
Below are the steps involved:
- Initialize a count variable, count = 0.
- Iterate over array arr:
- if arr[i] == 0, increment in count by 1.
- To count number of pairs possible:
- (count * (count -1 ) ) / 2, will be the final ans.
Below is the implementation of the above code:
C++
// C++ Implementation #include <bits/stdc++.h> #include <iostream> using namespace std; // Function to count number of pairs // whose bitwise XOR and AND are equal int BitByBit( int arr[], int n) { int i = 0; int count = 0; // Iterate over array while (i < n) { // If arr[i] = 0 if (arr[i] == 0) { count++; } i++; } // Number of pairs return (count * (count - 1)) / 2; } // Driver code int main() { int n = 5; int arr[] = { 1, 0, 0, 2, 2 }; // Function call cout << BitByBit(arr, n); return 0; } |
Java
public class BitwisePairs { // Function to count number of pairs // whose bitwise XOR and AND are equal static int bitByBit( int [] arr, int n) { int i = 0 ; int count = 0 ; // Iterate over array while (i < n) { // If arr[i] = 0 if (arr[i] == 0 ) { count++; } i++; } // Number of pairs return (count * (count - 1 )) / 2 ; } // Driver code public static void main(String[] args) { int n = 5 ; int [] arr = { 1 , 0 , 0 , 2 , 2 }; // Function call System.out.println(bitByBit(arr, n)); } } |
Python3
# Python Implementation # Function to count number of pairs # whose bitwise XOR and AND are equal def BitByBit(arr, n): i = 0 count = 0 # Iterate over array while i < n: # If arr[i] = 0 if arr[i] = = 0 : count + = 1 i + = 1 # Number of pairs return (count * (count - 1 )) / / 2 # Driver code if __name__ = = "__main__" : n = 5 arr = [ 1 , 0 , 0 , 2 , 2 ] # Function call print (BitByBit(arr, n)) # This code is contributed by Sakshi |
C#
using System; public class Solution { // Function to count number of pairs // whose bitwise XOR and AND are equal static int BitByBit( int [] arr, int n) { int i = 0; int count = 0; // Iterate over array while (i < n) { // If arr[i] = 0 if (arr[i] == 0) { count++; } i++; } // Number of pairs return (count * (count - 1)) / 2; } // Driver code public static void Main() { int n = 5; int [] arr = { 1, 0, 0, 2, 2 }; // Function call Console.WriteLine(BitByBit(arr, n)); } } // This code is contributed by akshitaguprzj3 |
Javascript
// JS Implementation // Function to count number of pairs // whose bitwise XOR and AND are equal function bitByBit(arr) { let count = 0; // Iterate over array for (let i = 0; i < arr.length; i++) { // If arr[i] = 0 if (arr[i] === 0) { count++; } } // Number of pairs return (count * (count - 1)) / 2; } // Driver code const arr = [1, 0, 0, 2, 2]; // Function call console.log(bitByBit(arr)); // This code is contributed by Sakshi |
Output
1
Time Complexity: O(N)
Auxiliary Space: O(1)