Problem Link : Xor – Sequence
Solution :
From the Hacker Rank editorial:
Let’s have a look at array A:A1=1
A2=1⊕2
A3=1⊕2⊕3
A4=1⊕2⊕3⊕4
A5=1⊕2⊕3⊕4⊕5
…
Now, let’s make array B where Bi=A0⊕A1⊕A2⊕…⊕Ai.
Bi=A0⊕A1⊕A2⊕…⊕Ai−1⊕Ai=Bj⊕Aj+1⊕Aj+2⊕…⊕Ai. For any 0≤j<i.
So AL⊕AL+1⊕…⊕AR=BL−1⊕BR.Now, let's have a look at array B:
B1=1
B2=2
B3=1⊕3
B4=2⊕4
B5=1⊕3⊕5
B6=2⊕4⊕6
B7=1⊕3⊕5⊕7
B8=2⊕4⊕6⊕8
It’s easy to observe that in odd indexes Bi=1⊕3⊕5⊕…⊕i
and for even indexes Bi=2⊕4⊕6⊕…⊕ifor even indexes there are numbers from 1 to i/2 multiplied by 2, that means bit’s are moved to left by 1, so, Bi=2⊕4⊕6⊕…⊕i=(1⊕2⊕3⊕…⊕i/2)∗2.
And for odd indexes there are numbers from 0 to (i−1)/2 multiplied by 2 and plus 1. That means bit’s are moved to left by 1, and last bit is made 1. so, Bi=1⊕3⊕5⊕…⊕i=(0⊕1⊕2⊕…⊕(i−1)/2)∗2+X.
X is 1⊕1⊕1⊕..⊕1 “ones” are repeated (i−1)/2+1 times. So, if (i−1)/2+1 is odd then X=1 else X=0.Now, calculation of 1⊕2⊕3⊕…⊕x.
Let’s prove that (4K)⊕(4K+1)⊕(4K+2)⊕(4K+3)=0 for 0≤K.
My code:
/*
*************************
Id : Matrix.code
Task: Xor-sequence
Date: 2016-02-01
**************************
*/
#include <bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
/*------- Constants---- */
#define Long long long
#define ull unsigned long long
#define mod 1000000007
#define MEMSET_INF 63
#define MEM_VAL 1061109567
#define forn(i,n) for( int i=0 ; i < n ; i++ )
#define mp(i,j) make_pair(i,j)
#define lop(i,a,b) for( int i = (a) ; i < (b) ; i++)
#define pb(a) push_back((a))
#define SZ(a) (int) a.size()
#define all(x) (x).begin(),(x).end()
#define gc getchar_unlocked
#define PI acos(-1.0)
#define INF 1<<29
#define EPS 1e-9
#define Fr first
#define Sc second
#define Sz size()
#define lc ((n)<<1)
#define rc ((n)<<1|1)
#define db(x) cout << #x << " -> " << x << endl;
#define Di(n) int n;si(n)
#define Dii(a,b) int a,b;si(a);si(b)
#define Diii(a,b,c) int a,b,c;si(a);si(b);si(c)
#define Si(n) si(n)
#define Sii(a,b) si(a);si(b)
#define Siii(a,b,c) si(a);si(b);si(c)
#define min(a,b) ((a)>(b) ? (b) : (a) )
#define max(a,b) ((a)>(b) ? (a):(b))
/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
typedef vector<Long> vl;
/*------ template functions ------ */
#ifndef getchar_unlocked
#define getchar_unlocked getchar
#endif
template<class T> inline void si(T &x){register int c = gc();x = 0;int neg = 0;for(;((c<48 | c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
Long bigmod(Long p,Long e,Long M){Long ret = 1;for(; e > 0; e >>= 1){if(e & 1) ret = (ret * p) % M;p = (p * p) % M;} return ret;}
Long gcd(Long a,Long b){if(b==0)return a;return gcd(b,a%b);}
Long modinverse(Long a,Long M){return bigmod(a,M-2,M);}
void io(){freopen("/Users/MyMac/Desktop/in.txt","r",stdin);}
/*************************** END OF TEMPLATE ****************************/
const int N = 1001;
Long xo(Long t)
{
if(t%4==0) return t;
if(t%4==1) return 1;
if(t%4==2) return t+1;
if(t%4==3) return 0;
return 0;
}
Long xol(Long a)
{
if(a%2 == 0) {
auto k = a/2;
k = xo(k);
return k * 2;
}else {
auto k = a/2;
k = xo(k);
return k * 2 + (((a/2) %2) == 0);
}
return 0;
}
int main()
{
Di(q);
for(int i= 0;i < q; i ++) {
Long l,r;
cin >> l >> r;
cout << (xol(r) ^ xol(l-1)) << endl;
}
return 0;
}
Code for Fun 