# CENS20D - Editorial

Testers: Jatin Nagpal

CAKEWALK

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: 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)
3 Likes

The brackets Chico, they never lie

7 Likes

Will you post solution to bonus?

Arenโt you using an array?

A very simple optimized brute force would work for constraints like N=10^5, and A[i]<=100.
Store every element in a set, and for every element check how many number in the range 1<=x<=100, give bitwise AND equal to x, and in the same time exist in the array.

1 Like

Can you explain how??

Omah god yes!

1 Like

if we use any space other than given space like queue,stack,etc then space comes into picture otherwise,O(1)

1 Like