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)
