Editorial for XORNEY - PELT2019

Question Code: XORNEY

Prerequisites: Implementation

Problem Setter: tds115

Difficulty: Cakewalk

Explanation:
Given two integer l and r, you have to find if xor from l to r is even or odd. Basically, you have
to find the number of odd integer between l and r. Since xor of odd 1’s is 1 and xor of even
1’s is 0. You can make 2 cases:-
(Let count be the number of odd’s)
If l is even and r is even-> count=(r-l)/2
Else → count=(r-l)/2+1
If count is even then ans is even
Else odd.

Complexity-O(1) for each query

Author’s solution: GUjqC5 - Online C++0x Compiler & Debugging Tool - Ideone.com

2 Likes

Given that this is a simple problem, it probably needs a more basic explanation.

If we have a “running total” that we are xor’ing numbers into, the parity (even/odd) only changes when we xor an odd number into it, because parity only depends on the bottom binary bit.

One odd number makes the running total odd; two odd numbers flip it back to even.

So - as you say - we are determining how many odd numbers there are between L and R inclusive.

If L & R are both even, this is easy: (R-L)/2 gives the number of odd numbers in range (try it!)

If L is odd, we can drop L down to the even number below (L-1) without changing the count of odd numbers in range. And if R is odd, we can increase R to the even number above without changing the count. So we can get to two even numbers to use the above formula.

And we can do those adjustments automatically using modulo results (%), since a%2 is zero for even a. So we can take C = ((R+R%2) - (L-L%2)) /2 for the count of odd numbers in range.

Then the parity of C is the answer, C%2 == 0 is “Even” and C%2 == 1 is “Odd”.

1 Like
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int t = Integer.valueOf(br.readLine());
        while (t-- > 0)
        {
            String[] values = br.readLine().split(" ");
            long L = Integer.valueOf(values[0]);
            long R = Integer.valueOf(values[1]);
            
            // counting odd numbers
            long count = (R - L) / 2;
            if ((R % 2 != 0) || (L % 2 != 0))
                count = count + 1;
            System.out.println((count % 2 == 0) ? "Even" : "Odd");
        }
	}
}

Status: Runtime Error (NZEC)
What’s wrong?

1 Like

Isn’t it wrong
i mean try these testcases
2
3 3
4 4

the output should be
Even
Even

but your code will give
Odd
Even

which is not right i guess cause any number xored with itself will result in 0 which is considered as “Even”.

Please clarify my doubt.

You misunderstood the question I guess. The question is all about finding the parity of
l \oplus (l + 1) \oplus (l + 2) \oplus\ \dots\ \oplus r for a given pair of (l, r), l\le r.

So, for l = 3 and r = 3, the result of above expression is 3 which is \text{Odd}.

Similarly, for l = 4 and r = 4, result is 4 which is \text{Even}.

1 Like

Ohh okay I was xoring it again with itself as that was the starting and ending, but we don’t have to do that. Okay I got it
Thank you very much