XORIER - Editorial

general
, , ,
5

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

6

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)

7

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

8

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?

9

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.

10

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);
11

this fails for the last test case.can anyone help

12

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

13

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

14

I admire the trick of div by 4. Sneaky.

15

…Thanks !!

16

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

17

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.

18

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).

19

please help with this code

20

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

21

By parity I mean even or odd. 2 and 7 do not have same parity.

22

yeah I got that, but isn’t it parity is different than simple odd or even number?

23
1 Like
25

can you tell me why am i getting WA and what should i do to improve my code
https://www.codechef.com/viewsolution/35867431