# PROBLEM LINK:

*Author & Editorialist:* Saurabh Yadav

*Testers:* Jatin Nagpal

# DIFFICULTY:

CAKEWALK

# PREREQUISITES:

Brute force

# PROBLEM:

Given an array of size N, find the count of pairs such that a[i] = a[i] \& a[j], where j>i and & denotes bitwise AND.

# QUICK EXPLANATION:

Iterate over all possible pairs and count such pairs.

# EXPLANATION:

Let an element of array be a[i], now just iterate over the part of the array i.e i \lt j \lt n and find such a[j] whose bitwise AND with a[i] is equal to a[i].

## Common mistake

Why does a[i] \&a[j]==a[i] or a[i]==a[i ]\& a[j] give wrong answer in C++/Java ? The reason is operator precedence. Here the == operator is perfomed first and then \& operator is performed due to operator precedence, but we actually need the \& operation to be performed first and == operator afterwards. Therefore, always put a bracket around even if it is a cakewalk problem .

# TIME COMPLEXITY:

**Time**: O(N^2)

**Space**: O(1)

# BONUS PROBLEM:

## Bonus problem

Solve the same problem for N=10^5.

# SOLUTIONS:

## C++ Solution

```
#include<bits/stdc++.h>
using namespace std;
int32_t main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
cin >> a[i];
int ans = 0;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if ((a[i]&a[j]) == a[i])
ans++;
}
}
cout << ans << "\n";
}
return 0;
}
```

## Python Solution

```
t = int(input())
for _ in range(t):
n = int(input())
arr = [int(j) for j in input().split()]
ans = 0
for i in range(n):
for j in range(i+1, n):
if arr[i]&arr[j] == arr[i]:
ans += 1
print(ans)
```