PROBLEM LINK:
SETTER:
TESTER:
EDITORIALIST:
DIFFICULTY:
EASY
PREREQUISITES:
Xor Properties
PROBLEM:
Given L to R find the xor of L to R.
QUICK EXPLANATION:
Let say XOR (Y) = 1 ⊕ 2 ⊕ 3 …⊕ Y
If we can find the value of XOR ( R ) and XOR ( L-1 ) then we can easily find the required answer by doing XOR ( L-1 ) ^ XOR ( R ).
EXPLANATION:
As constraints are very big in this problem so we can’t run loop for finding XOR ( R ) or XOR ( L ).
Trick to find XOR ( X ):
Xor of any 4 consecutive number is always 0
if X%4 \equiv 0 \bmod 4 then XOR ( X ) = X
if X%4 \equiv 1 \bmod 4 then XOR ( X ) = 1
if X%4 \equiv 2 \bmod 4 then XOR ( X ) = X + 1
if X%4 \equiv 3 \bmod 4 then XOR ( X ) = 0
Now we have XOR ( L -1 ) and XOR ( R ) we can easily calculate ( L )^( L+1 )+( L+2 )+…( R ).
SOLUTIONS:
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll fun(ll x){
if(x==0)return 0;
ll n=x;
x%=4;
if(x==0)return n;
if(x==1)return 1;
if(x==2)return n+1;
if(x==3)return 0;
return 0;
}
void solve(){
ll l,r;
cin>>l>>r;
if(l==0 and r==0)cout<<0<<“\n”;
else if(l==0)cout<<fun(r)<<“\n”;
else cout<<(fun(l-1)^fun(r))<<“\n”;
}
bool imp=true;int main(){
ll t;
t=1;
if(imp)
cin>>t;
while(t–)
solve();
return 0;
}