Total pairs in an array such that the bitwise AND, bitwise OR and bitwise XOR of LSB is 1

Given an array arr[] of size N. The task is to find the number of pairs (arr[i], arr[j]) as cntAND, cntOR, and cntXOR such that: 

1. cntAND: Count of pairs where bitwise AND of least significant bits is 1.
2. cntOR: Count of pairs where bitwise OR of least significant bits is 1.
3. cntXOR: Count of pairs where bitwise XOR of least significant bits is 1.

Examples: 

Input: arr[] = {1, 2, 3} 
Output: 
cntXOR = 2 
cntAND = 1 
cntOR = 3 
Array elements in binary are {01, 10, 11} 
Total XOR pairs: 2 i.e., (1, 2) and (2, 3) 
Total AND pairs: 1 i.e., (1, 3) 
Total OR pairs: 3 i.e., (1, 2), (2, 3) and (1, 3)

Input: arr[] = {1, 3, 4, 2} 
Output: 
cntXOR = 4 
cntAND = 1 
cntOR = 5 

Approach: 

1. To get the LSB of the elements of the array, first, we calculate the total even and odd elements. Even elements have LSB as 0 and odd elements have LSB as 1.
2. In order for 
   • XOR to be 1, LSB of both the elements have to be different.
   • AND to be 1, LSB of both the elements have to be 1.
   • OR to be 1, at least one of the elements should have it’s LSB as 1.
3. Therefore, total number of required pairs 
   • For XOR: cntXOR = cntOdd * cntEven
   • For AND: cntAND = cntOdd * (cntOdd – 1) / 2
   • For OR: cntOR = (cntOdd * cntEven) + cntOdd * (cntOdd – 1) / 2

Below is the implementation of the above approach:

cntXOR = 4
cntAND = 1
cntOR = 5

Time Complexity: O(N)
Auxiliary Space: O(1)