I am getting TLE continuously..Please help!!

Hello everyone, i am a beginner and this is my first question so please forgive any mistakes.

I am solving the question here-XORNEY Problem - CodeChef.
and i have tried alot of changes in the code but i am still getting TLE.

Here’s my code-

#include<bits/stdc++.h>

using namespace std;
int main(){

ios_base::sync_with_stdio(false);
cin.tie(NULL);

long int t,i;
cin >> t;

for(i=0;i<t;i++)
{
    long long l,r,j,xoor;
    cin >> l >>r;
    
xoor= l^(l+1) ;
    for(j=l+1; j<r; j++)
    {
        xoor = xoor^(j+1);

    }
    if((xoor&1)  == 0)
    cout << "Even" << "\n";
    else
    cout << "Odd" << "\n";
}

return 0;

}

Thanx in advance…!

See the constraints on L and R. They can go upto 10^{18}. You can’t run a loop of these many iterations. Also T is as large as 10^6. So you need an algorithm which can find XOR of a range [l, r] within constant or logarithmic time.
But the actual problem is to find whether XOR will be Even or Odd. We know that XOR of 2 even numbers or 2 odd numbers is even. Why? Because last bit of both numbers will be either 0(in case of both even) or 1(in case of both odd). So XOR of last bit will be 0 that means Even. So now we just need to see how many even numbers and how many odd numbers are there in the range [l, r]. If both L and R are odd that means count of Odd numbers is one more than even. So total count of odd numbers is (R-L)/2+1. Otherwise count of Odd numbers is (R-L+1)/2. So if count is Odd then XOR is Odd otherwise Even.
See this.

1 Like