Count pairs with bitwise AND greater than or equal to XOR

You are given a positive integer n, and an array a of positive integers. Find number of such pairs (i,j) such that i<j and a_i & a_j≥ a_i ^ a_j, where & denotes the bitwise AND operation, and ^ denotes the bitwise XOR operation.

Examples :

Input :
5
1 4 3 7 10
Output : 1
Explanation :
There is only one pair - (4,7) such that 4&7=4 and 4^7=3

Input :
4
6 2 5 3
Output : 2
Explanation :
There are two pairs - (6,5) and (2,3) such that a[i]^a[j]
<=a[i]&a[j]
there are two pairs: (6,5) and  (2,3)

Naïve approach: A Naïve solution to solve this problem is to generate all pairs (i, j) such that i<j and for every pair, we will check for the condition whether a[i] & a[j] is greater than or equal to a[i] ^ a[j].

Steps to follow:

For every pair, simply check the condition a[i] & a[j] >= a[i] ^ a[j] for all pairs (i, j) such that i<j.

Below is the implementation for the above approach:

//Here is the C++ code for the naive approach

#include <bits/stdc++.h>
using namespace std;

int countPairs(int arr[], int n) {
	int count = 0;
	for(int i = 0 ; i < n ; i++) {
		for(int j = i + 1 ; j < n ; j++) {
			if( ( (arr[i]) & (arr[j]) ) >= ( (arr[i]) ^ (arr[j]) ) )
				count++;
		}
	}  
	return count;
}

int main() {
  	int n = 4;
	int arr[] = {6, 2, 5, 3};
	cout << countPairs(arr, n) << endl;
	return 0;
}

Time Complexity : O(N^2), where N is the size of array.

Space Complexity : O(1)

Efficient approach :

We use the concept of bits here.
The idea is simple, two numbers a, b satisfies the condition a & b >= a ^ b only if both a and b have MSB bit as set(1).
We check for all possible bits positions that is 0 to 31st bit.
Also we maintain a bool vector to make sure any number is not counted twice.

Implementation :

//Here is the C++ code for the above efficient approach

#include <bits/stdc++.h>
using namespace std;

int countPairs(int arr[], int n){
	vector<bool> visited(n, false);
	int result = 0;
	for(int i = 31 ; i >= 0 ; i--) {
		int count = 0;
		for(int j = 0 ; j < n ; j++) {
			if ( (1<<i) & (arr[j]) && !visited[j]) {
				visited[j] = true;
				count++;
			}
		}
		result += ( count * (count - 1)) / 2; //Adding total different pairs possible
	}
	return result;
}

int main(){
	int n = 4;
	int arr[] = {6, 2, 5, 3};
	cout << countPairs(arr, n) << endl;    
	return 0;
}

Time Complexity : O(N), where N is the size of given array