XORAND Editorial

editorial
, , , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Lavish Gupta
Tester: Aryan, Takuki Kurokawa
Editorialist: Pratiyush Mishra

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Alice has an array A of length N. She is interested in finding the number of pairs (i,j) such that 1≤i<j≤N and A_i \oplus A_j<A_i\; \& \;A_j

\oplus represents the Bitwise XOR operator. \& represents the Bitwise AND operator.

Explanation

Taking two elements from the array, say A_i and A_j and assuming their most significant bit to be x and y respectively. Then if,

x = y\; => A_i\;\oplus\;A_j < A_i \;\&\; A_j

Now if we group the elements having same most significant bits, then in each such group if we pick any two elements, say A_i and A_j then for them A_i\;\oplus\; A_j < A_i\; \& \; A_j.

Total number of ways of picking any two elements from a group of size N is:

{N \choose 2} = \frac{N(N-1)}{2}

Thus we would sum up all possible pairs from each group to get the final answer.

Suppose from the given array we form corresponding groups as \{G_1,G_2, G_3........G_k\} where the size of of the group say, G_i is g_i, then

Ans = \sum_{i=1}^{i=k} {g_i \choose 2}

TIME COMPLEXITY:

Calculation of the MSB position of a number can be done in O(1) time. Further looping through the array to calculate MSB and grouping them can be done in O(N) time. Thus final time complexity of the solution would be O(N)

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester-1’s Solution
Tester-2’s Solution

1 Like
2

The problem could be searched via simple google search. Link - A. Find Pairs | Practice Problems

@admin

4 Likes
3

Before being used in a contest, problems should be vetted. @admin

1 Like
4

We missed this one somehow. Apologies for that.

5

My code fails the last test case. Here is the code. Please help by providing the edge case.

6

Please help by providing readable code.

3 Likes
7

bro at line no.112 you have declared your variable ‘l’ as int and after multiplying l*(l-1) its vaue overflow and you can’t store that in your ans variable.
you should make l as long type or multiply l*(1ll)* (l-1)
same mistake done by my friend and he got it after 1 min of ending the contest.

8

I got Wrong answer in this code

#include"bits/stdc++.h"
using namespace std;
using ll = long long;
ll nc2(ll n)
{
	return n * (n - 1) / 2;
}
void solve()
{
	ll n; cin >> n;
	vector<ll> a(n);
	for (ll i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	vector<ll> count(10, 0LL);
	for (ll i = 0; i < n; i++)
	{
		for (int j = 9; j >= 0; j--)
		{
			if (a[i] & (1 << j) )
			{
				count[j] += 1;
				break;
			}
		}
	}

	ll ans = 0;
	for (int i = 0; i < 10; i++)
	{
		ans += nc2(count[i]);
	}
	cout << ans << "\n";

}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	long long int t; cin >> t; while (t--)
	{solve();}

return 0;

}

But when i change the limit of my count[] vector to 32 it got ACCEPTED
Since In the problem It clearly states that value of Ai<1e9 then when do i have to check number as big as 2^32

9

1mbuh7

10

I didn’t get one thing in video editorial that how the msbcount can be 0
We first found the msb of the given array elements then at last we checked for the number of same msbpositions so it will be atleast one because if we are checking for it that means we have already been here and also i didn’t get why we did in msbcount[msb]-1
Please help

11

Bit operations are done using the binary representation of a number. The maximum values of Ai is given to be 1e9. Convert this number to binary and see how many digits is it taking. Also check what’s the maximum number using you can obtain using 10 digits in binary representation (all 1s). Should clear your doubt up.

12

yes thanks it cleared my doubt

13

Thanks @ashutosh251848 . It worked. If you can elaborate a little more , as i understand int * int might overflow, thats why i store that part in long ,
long sum= l * (l-1) ; why the need to also declare l as long.

14

gfg article overflow
hey! when you are multiplying int with int it will first store as int then it will be stored in ans variable, so when it overflows randomly some number is stored in ans. that’s why either you should make your l as long type or multiply l*(l-1) with 1l so that it is calculated in long and then stored in long data type.
It will be more clear if you read GFG article i have added in this comment.

1 Like
15

exactly
specially when it is obvious that many divison 3 programmer will also be viewing the editorial

16

Hey , thanks , learn something new today. Thanks again.

17

last case test for integer overflow

18

Hey @akashagarwal00
Thanks for asking your doubt.

Yes, you are correct msbcount cannot be 0.