Given Q queries consist L and R find XOR of every consecutive charachter between L and R
constraint 1<=L
So, We cannot use brute force approach here because this will give us TLE.
now there's an interesting pattern in XOR between 1to N is
1^2^3^4^5^6^7^8
{1 3 0 4 }{1 7 0 8}
{1 n+1 0 n}
so using this property we can easily find XOR till nth number in O(1) constat time
by [(num-1)%4+1] and assign its value as 1->1, 2->N+1,3->0,4->N
Now problem is to solve XOR between L to R
L^(L+1)^(L+2)^...^(R-1)^(R)
and we know property X^X=0;
so, using this property we can find XOR between L and R by
XOR(till R)^XOR(till L)
eg L=5,R=8
1^2^3^4^5^6^7^8^
1^2^3^4
so we are left with 5^6^7^8
and we can calculate this by XOR(R)^XOR(L-1) in constant time.
Top comments (0)