|
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=0
Input: 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++
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
int BitByBit(int arr[], int n)
{
int i = 0;
int count = 0;
while (i < n) {
if (arr[i] == 0) {
count++;
}
i++;
}
return (count * (count - 1)) / 2;
}
int main()
{
int n = 5;
int arr[] = { 1, 0, 0, 2, 2 };
cout << BitByBit(arr, n);
return 0;
}
|
Java
public class BitwisePairs {
static int bitByBit(int[] arr, int n) {
int i = 0;
int count = 0;
while (i < n) {
if (arr[i] == 0) {
count++;
}
i++;
}
return (count * (count - 1)) / 2;
}
public static void main(String[] args) {
int n = 5;
int[] arr = {1, 0, 0, 2, 2};
System.out.println(bitByBit(arr, n));
}
}
|
Python3
def BitByBit(arr, n):
i = 0
count = 0
while i < n:
if arr[i] == 0:
count += 1
i += 1
return (count * (count - 1)) // 2
if __name__ == "__main__":
n = 5
arr = [1, 0, 0, 2, 2]
print(BitByBit(arr, n))
|
C#
using System;
public class Solution
{
static int BitByBit(int[] arr, int n)
{
int i = 0;
int count = 0;
while (i < n)
{
if (arr[i] == 0)
{
count++;
}
i++;
}
return (count * (count - 1)) / 2;
}
public static void Main()
{
int n = 5;
int[] arr = { 1, 0, 0, 2, 2 };
Console.WriteLine(BitByBit(arr, n));
}
}
|
Javascript
function bitByBit(arr) {
let count = 0;
for (let i = 0; i < arr.length; i++) {
if (arr[i] === 0) {
count++;
}
}
return (count * (count - 1)) / 2;
}
const arr = [1, 0, 0, 2, 2];
console.log(bitByBit(arr));
|
Time Complexity: O(N)
Auxiliary Space: O(1)
|
