XORIER - Editorial

PROBLEM LINK:

Div1
Div2
Practice

Setter- Priyanshi Gupta
Tester- Teja Vardhan Reddy
Editorialist- Abhishek Pandey

DIFFICULTY:

EASY

PRE-REQUISITES:

Goldbach’s Conjecture , Frequency array concept, Properties of XOR.

PROBLEM:

Given an array A of N numbers, we need to tell number of pairs of indices (i,j) such that -

  • 1 \le i < j \le N (1 based indexing)
  • A_i \oplus A_j can be written as sum of 2 prime numbers of same parity.

QUICK-EXPLANATION:

Key to AC- Deducing 2 facts-
1. XORing numbers of same parity always results in even numbers. And adding prime numbers of same parity results in even numbers as well.
2. Correlating above to Goldbach’s conjecture which says any even number >2 can be represented as a sum of 2 primes.

Deducing above 2 was was the main turning point, and difference between a quick AC and complete cluelessness.

Quick Explanation- Focus on what the question says. It first says that, A_i \oplus A_j must be representable as a sum of prime numbers of same parity. Its basic math that adding two numbers of same parity results in a sum of even parity (i.e. Odd+Odd=Even. Even+Even=Even). Also, the same rule holds for XOR.

Appplying Goldbach’s conjecture, the question reduces to find how many pairs (i,j) exist such that-

  • Their XOR is even.
  • Their XOR is greater than 2.

For XOR being even, we check only among pairs with same parity. For XOR being greater than 2, we first find number of all possible even XOR values, and then reduce count of XORs with value 2 and 0. This can be done easily via frequency array.

EXPLANATION:

The explanation will have a single section explaining editorialist’s solution. Some proofs are left as in exercise to reader - their answers can be found in my bonus corner at the end of editorial. Try to read the editorial in a way to capture the thought process going in mind of a coder, because often we all know and are aware of things but fail at application in correct form. I assume you are thorough with basic properties of XOR. Please read them under pre-requisites if its not the case!

Editorialist’s Solution-

Lets first discuss the solution of first sub-task for formality. The idea of first subtask is to use 2 nested loops, and try out all the possible \frac{N*(N-1)}{2} values of i and j. If their XOR is even and greater than 2, add 1 to answer.

Now, before moving towards the full solution, grasp the 3 rules I say below. If having trouble, try to prove them or check out proofs in the bonus corner below. Then, proceed once you have proper clarity about those.

1. Only the rightmost bit (i.e. Least-significant bit or LSB) determines whether a number is odd or even.
2. Using above rule, conclude that XOR of numbers of same pairty is always even. (i.e. Even \oplus Even=Even and Odd \oplus Odd=Even)
3. Read Goldbach’s Conjecture, which says, " that every even integer greater than two is the sum of two prime numbers.". Do NOT try to prove it. This conjecture is still unproven and its proof is one of mysteries, but the results have been verified to hold true for numbers even larger than 4*{10}^9. Hence, it holds good in the range of input which we have.

With above 3, we can get a hint of implementation in mind. We need a count of numbers which are odd, and which are even (so that their XOR is always even).

After that, we have to check that the equivalent XOR is greater than 2. If it is, then by Goldbach’s conjecture, any even number greater than 2 satisfies our condition of being a sum of 2 primes of same parity. Now, this part is where most of contestants face problem - usually because they never did a similar problem before.

Newbies get overwhelmed by “Ok its easy to make sure that XOR is even, but how do I assure that its greater than 2 and include only proper indices in my answer?!”

The answer is simple, dont! The proper methodology is to, first find the answer including repetitions and pairs with XOR \le 2 as well, and later subtract irrelevant ones from answer. (You can find a note about it in point 3. of my corner.) Making sure that XOR is >2 on the run is difficult. Instead, first just count how many pairs (i,j) are there such that A_i \oplus A_j is even. That is easy, right? Make it easier, for now, forget about restriction of 1 \le i < j \le N, just find any pair (i,j) such that 1 \le i,j \le N. Any pair will do, no constraints on i and j. Can you do that, if you are given the array A and know how many numbers in it are odd and how many numbers are even? (Check out tab below to see how if cannot).

Click to view

Since there is no restriction on (i,j), we can simply follow below-

for(i=0;i< n;i++)
	    {
	        if(arr[i]%2==1)//If number is odd
                     ans+=odd;//Odd= number of odd elements in array
	        else //If number is even
                     ans+=even;//even =number of even numbers in array.
           }

The logic is that, if my A_i is odd, then I have odd (odd= number of odd elements in array) choices of indices to pick currently such that the resultant XOR is even, hence I add odd to answer. If A_i is even, then I have even choices of indices to pick, where even represents number of even number in array as shown in above code. I add that to answer.

Now, we have the answer in crude form, what we have to do is to account for repetition of pairs (we counted (2,1) and (1,2) differently, which makes our answer twice the expected one), which can be easily done by halving the answer in the end.

First, we have to take care of cases when XOR comes out to be 2 or 0 (i.e. even number \le 2). This is also simple! For this, maintain a frequency array, and now count how many times each number occurs.

Now, think to yourself, for every element in array A_i, how many choices do I have to choose j such that 1 \le i,j \le N and A_i \oplus A_j=2 ? Lets use b to represent all numbers such that b \oplus A_i=2. We find that b=A_i \oplus 2. (Proof given in tab below). Hence, all we have to do is to subtract the count of numbers with value A_i \oplus 2 to account for numbers having XOR=2!!

Click to view

We have-

b \oplus A_i=2

Xoring both sides with A_i-

b \oplus A_i \oplus A_i=2 \oplus A_i

Xor can be done in any order. Also, its known that, for any number K, K \oplus K=0. Hence, the above becomes-

b \oplus (A_i \oplus A_i)=2 \oplus A_i
\implies b \oplus 0=2 \oplus A_i
\implies b = 2 \oplus A_i

This also means that b is unique for a given A_i

Similarly, to account for numbers with XOR 0, we think of how many choices do I have to choose pairs (i,j) under same conditions (as above) such that A_i \oplus A_j=0. It is very easy to see that, if we use b to represent choices of numbers such A_i \oplus b=0, then this will imply that b= A_i. Hence, we simply reduce frequency of A_i from our crude answer.

(Check out above proof and try to follow exact guidelines to derive this, if in confusion how we concluded this. The steps to be followed are exact same!).

In the end, as I mentioned above, after accounting for XORS resulting in 2 and 0, we simply halve the answer to get the final answer to print :slight_smile: .

As an exercise, try to write down an implementation of above idea in pen and paper. A code to compare your implementation with is given below as answer-

One warning though, make sure to declare your frequency array larger than size 1000001 so that you dont get out of bounds when checking for count of A_i \oplus 2

Click to view
//Odd^Odd=Even. Even ^ Even=Even. ^=XOR operation.
	    for(i=0;i<n;i++)
	    {
	        if(arr[i]&1)ans+=odd;
	        else ans+=even;
	        ans-=freq[arr[i]^2];//Remove count of elements by which XOR is 2
	        ans-=freq[arr[i]];//Remove count of elements by which XOR is 0.
	    }
	    cout<<(ans>>1)<<endl;//Divide answer by 2 as we doubly counted. i.e. we took (1,2) different 
        //from (2,1).
	    //Hence, half the answer out for exact required number.

SOLUTION

The respective codes are also pasted in tabs below in case the links do not work. This is for convenience of readers, so that they can copy paste it to whichever IDE or editor they are comfortable reading it in and immediately have access to the codes. :slight_smile:

Author’s solution can be found here.

Tester

Click to view
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
int a[123456],b[1234567];
int cnt[123];
int main(){
    std::ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
    	int n;
    	cin>>n;
    	int i;
    	ll ans=0;
        // b[i] counts occurence of i so far.
    	rep(i,1234567){
    		b[i]=0;
    	}
        // cnt  counts number of even and odd numbers so far.
    	rep(i,5){
    		cnt[i]=0;
    	}
        // Using goldbach principle all even numbers more than 3 can be written as sum 
        // of primes (Since number is even, both primes should have same parity).
        // Now in odd case, parity will always be different.
    	rep(i,n){
    		cin>>a[i];
            // cnt of same parity numbers, becuase xor with them will give even number.
    		ans+=cnt[a[i]%2];
    		// but we dont want it to zero
            ans-=b[a[i]];
            // but we dont want it to two
    		ans-=b[(a[i]^2)];
    		b[a[i]]++;
    		cnt[a[i]%2]++;
    	}
    	cout<<ans<<endl;
 
 
    }
    return 0;   
}

Editorialist

Click to view
/*
 *
 ********************************************************************************************
 * AUTHOR : Vijju123                                                                        *
 * Language: C++14                                                                          *
 * Purpose: -                                                                               *
 * IDE used: Codechef IDE.                                                                  *
 ********************************************************************************************
 *
 Comments will be included in practice problems if it helps ^^
 */
 
 
 
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
 
 
int main() {
	// your code goes here
	#ifdef JUDGE
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    #endif
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	srand(time(NULL));
	int t;
	cin>>t;
	while(t--)
	{
	    int n;
	    cin>>n;
	    int i,arr[n],freq[1100001]={0};//Frequency array
	    for(i=0;i<n;i++)
	    {
	    	cin>>arr[i];
	    	freq[arr[i]]++;//update frequency of number
	    }
	    long long odd=0,even=0,ans=0;
	    for(i=0;i<n;i++)//Count how many odd and even numbers are there
	    {
	    	if(arr[i]&1)
	    		odd++;
	    	else 
	    		even++;
	    }
	    //Odd^Odd=Even. Even ^ Even=Even. ^=XOR operation.
	    for(i=0;i<n;i++)
	    {
	        if(arr[i]&1)ans+=odd;
	        else ans+=even;
	        ans-=freq[arr[i]^2];//Remove count of elements by which XOR is 2
	        ans-=freq[arr[i]];//Remove count of elements by which XOR is 0.
	    }
	    cout<<(ans>>1)<<endl;//Divide answer by 2 as we doubly counted. i.e. we took (1,2) different from (2,1).
	    //Hence, half the answer out for exact required number.
	}
	return 0;
}

Time Complexity=O(N)
Space Complexity=O(N)

CHEF VIJJU’S CORNER :smiley:

1. Proof Only LSB determines pairty.

Click to view

Represent the number in Binary. Let me represent bit at i'th index from right by b_i and used 0-based indexing. Hence, LSB is represented by b_0. Now, recall how do we convert a number from binary to decimal. Say I give you (1101)_2 and ask to write its decimal equivalent, what will you do? You will say, that the decimal number is equal to (2^0+2^2+2^3=8+4+1=13). Now, stop there and observe one thing. Except 2^0, all numbers are even! And guess where this 2^0 comes from? Yes, LSB!

Now we know that Even+Odd=Odd and Even+Even=Even. If LSB is 1, we will have to add 2^0=1 in the answer. All of the rest numbers will be of form 2^i and have i\ge 1 and hence be even. Hence, only LSB will determine if an odd number (i.e. 1) will be added to current sum (which is even) or not, and hence determines parity.

2. XOR of same parity is always even.

Click to view

Parity depends only on the LSB. Lets consider 2 cases, when LSB of both numbers if 1, and when it is 0 for both of them.

Take below 2 numbers as example for first case-
1010101 \oplus 10001.

We only care about LSB as we are interested in pairty. In this case, it’d be 1 \oplus 1=0. Similarly, in other case, when LSB of both is 0, it’d be 0 \oplus 0=0.

If numbers are not of same parity, the LSB of one number will be 1 and of other will be 0. XORing them, we will find LSB of result to be 1 \oplus 0= 0 \oplus 1=1 which is odd.

3. LoEE-

Click to view

Law of Easy Elimination: This is a methodology coders follow when they see following properties in answer-

  • Calculating answer at once, is difficult. However, a crude answer, which may include invalid pairs and/or repetitions can be easily found.
  • It is easier to eliminate the invalid pairs and repetitions from crude answer, than to acccount for them on the run at once while calculating answer.

In this methodology, we first calculate the crude answer first, and then proceed to find final answer by subtracting invalid pairs and/or repetitions.

4. Related problems - The only reason newbies are not able to solve problems on frequency array topic is because of lack of practice. Practice these problems till the process becomes completely mechanical and intuitive for you. :slight_smile:

  • AVGPR - Another question on Frequency array. You can find more problems in my editorial of this problem :slight_smile:
1 Like

What I did in this problem is :

→ Split input in two arrays

  1. odd
  2. even

→ Divide each number by 4 (removing last two bits)

why?
Reason :

Click to view

Now, we have to delete pairs which have Xor either 0 or 2 (i.e less than 4)

Think then when can Xor be 0 , 2 ???

Answer : when all bits of both numbers are equal except last two bits !!

explanation : (for above claim) Xor simple means 0 if corresponding bit are 0 and 1 if they are different

i.e. 1010 \oplus 1100 = 0110 (bits which are different in both is 1 and others are 0)

Now , Xor = 2_{10} = 0010_2 and Xor = 0_{10} = 0000_2

So xor= 2 or xor=0 means all bits except last(right most) two bits are equal…

So why not just remove these two bits ?

Now for both arrays (odd and even )

Count freq of each element in array of size 10^6/4 +1 (range/4 as I have divided each value by 4)

Do : ans= { n \choose 2 } (n is size of each array)

Then: ans-= \sum_{k=0}^{k=10^6/4} { freq(k) \choose 2}

That is nothing but,

all possible pairs { n \choose 2 } - pairs whose xor is 0 or 2 ( { freq(k) \choose 2} for each k )

Simple Implementation in c++ can be found HERE

4 Likes

how can i reduce the time required for this execution…?

https://www.codechef.com/viewsolution/20227441

Goldbach’s conjecture was proved upto 4*10e18 :slight_smile:

1 Like

For me, I first created a frequency array, and also split the input array into two arrays:

  1. an array of even numbers
  2. an array of odd numbers.

I then sorted the two arrays(I will latter on apply binary search), and performed the following steps:

  1. calculate number of odd pairs, “oddPairs” using (n(n+1)/2)-n, and add it to number of even Pairs, “evenPairs”.
  2. calculate number of pairs whose XOR is 0, “zeros” from the frequency array
  3. calculate number of pairs whose XOR is 2, “nparity”, by applying binary search on both even and odd arrays.
  4. And finally subtracting (zeros + nparity) from (oddPairs + evenPairs)

There were a few observations which I made, leading to my decision to apply binary search:

  1. If a is even then a^(a + 2) is 2 only if a/2 is even, and a^(a - 2) is 2 if otherwise.
  2. If a is odd then a^(a + 2) is 2 only if (a+1)/2 is odd, and a^(a - 2) is 2 if otherwise.

So the way I calculated the pairs whose XOR is 2 was by applying binary search separately on each sorted array, starting from the first number a[1] in the array, I would then search for either (a + 2) or (a - 2) depending on the above observations, and then marking all indexes from (a + 2) onwards or (a - 2) onwards as seen, so that those indexes wouldn’t be latter on visited.
Here’s my solution CodeChef: Practical coding for everyone

3)calculate number of pairs whose XOR is 2, “nparity”, by applying binary search on both even and odd arrays.
it requires 2 for loops right(order of n)

https://www.codechef.com/viewsolution/20237335
In my implementation, instead of halving the value at the end. I have decremented the frequency and odd or even before each iteration. So, can anyone point out which case did i miss. Thanks in Advance

I got WA for the following code:

https://www.codechef.com/viewsolution/20244104

Can someone please suggest me a testcase for which this code fails?

for better clarity one can use structures, as i have used.
check out thislink text https://www.codechef.com/viewsolution/20240933code and u will understand everything.

int n = scn.nextInt();
long[] arr = new long[n];

		int odds = 0;
		int evens = 0;

		HashMap<Long, Long> map = new HashMap<>();
		for (int j = 0; j < n; j++) {
			arr[j] = scn.nextLong();
			if (arr[j] % 2 == 0) {
				evens++;
			} else {
				odds++;
			}
			if (map.containsKey(arr[j])) {
				map.put(arr[j], map.get(arr[j]) + 1);
			} else {
				map.put(arr[j], 1l);
			}
		}
		long totalPair = ((n) * (n - 1)) / 2;
		long evenOddPairs = evens * odds;

		// these pairs have xor even >	
		long onlyEvenOrOddPair = totalPair - evenOddPairs;

		long sameNoPair = 0;
		// remove pairs with xor zero
		ArrayList<Long> keyset = new ArrayList<Long>(map.keySet());
		for (int i = 0; i < keyset.size(); i++) {
			long aI = keyset.get(i);
			long freqI = map.get(aI);

			if (freqI > 1) {
				sameNoPair += ((freqI) * (freqI - 1)) / 2;
			}
		}

		long pairWithXorEqual2 = 0;
		for (int i = 0; i < keyset.size(); i++) {
			long aI = keyset.get(i);
			long freqI = map.get(aI);

			long aJ = aI ^ 2;

			if (map.containsKey(aJ)) {
				long freqJ = map.get(aJ);
				pairWithXorEqual2 += freqI * freqJ;
			}

		}

		pairWithXorEqual2 = pairWithXorEqual2 / 2;

		long ans = onlyEvenOrOddPair - sameNoPair - pairWithXorEqual2;
		System.out.println(ans);

this fails for the last test case.can anyone help

IN RESPONSE TO:https://discuss.codechef.com/questions/134985/xorier-editorial/135714

@ayush3890 Hi , I think we both have used similar approach , you can have a look at my code. If it helps.
https://www.codechef.com/viewsolution/20337606

Minor typo - “Goldbach”, not “Goldback” (in the prerequisites)

I admire the trick of div by 4. Sneaky.

…Thanks !!

Firstly, Python has an xor operation: a^b. No need to code your own. Then read the editorial and i_return’s answer.

No. It requires only 1 for loop. You first take a number a[i]. If it’s even, you divide it by two. If the result of the division is even it means that a[i]^(a[i] + 2) is 2. So you search for (a[i] + 2) using binary search. The search will either return -1 if (a[i] + 2) is not found, or the index of where it occurred. And since our arrays are sorted, we can get the number of times (a[i] + 2) is repeated.

We would have searched for (a[i] - 2) if the result of our division was odd.
On the other hand, if a[i] is odd, then we divide a[i]+2 by 2. If the result is odd, we search for a[i]+2, and if otherwise, we search for a[i]-2.

NOTE: Binary search is what is being applied here, and not linear search. So in the worst case (when there are no pairs whose XOR is 2), then we will have O(NlogN); in the best case (where the a[0] matches with the rest), then we have approximately O(logN).

please help with this code

what about 2 and 7 ? they both have even parity. Xor’ing them gives an odd number.