CENS20D - Editorial

PROBLEM LINK:

Practice
Contest

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 :stuck_out_tongue:.

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

The brackets Chico, they never lie :speak_no_evil:

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