You are not logged in. Please login at www.codechef.com to post your questions!

×

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-https://www.codechef.com/problems/XORNEY. 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..!

asked 10 Feb, 15:36

ps_01's gravatar image

0★ps_01
1
accept rate: 0%


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.

link

answered 10 Feb, 15:52

vichitr's gravatar image

5★vichitr
2555
accept rate: 11%

edited 10 Feb, 16:03

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×151
×23

question asked: 10 Feb, 15:36

question was seen: 110 times

last updated: 10 Feb, 16:03