An infinite array is defined as follows:
A[0]=0
A[i] = i xor A[i-1]

You have to answer Q queries.Each query comprises two integer L and R . You have to calculate XOR of all array elements of A between L and R(inclusive)

3
2 4
2 8
5 9

output
7
9
15

1<=Q<=10^5
1<=L<=R<=10^15
Problem asked in valuefy labs

I think you could start with finding F(0,R) and F(0,L-1).
Now for F(0,x), you could consider count of each bit that is ON in this range. For that consider the sequence below :
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
As you can see in this sequence bit 1 occurs at the gap of 1, bit 2 at gap of 2, bit 3 at gap of 4… etc.
Also bits occur with frequency of gap size when they do.
So I believe count of certain bit (numbered from LSB,1 based indexing) is :
floor((x+1) /(2^i))*(2^(i-1)) + max(0 , ((x+1) mod (2^i)) - 2^(i-1))
So count each bit’s frequency and if frequency is odd then only add 2^(i-1) to the F(0,x) .
After calculating for L-1 and R, just take bitwise xor and print it.

Edit : Sorry I didn’t read the question completely, but after reading it again, I believe approach remains identical, the formula changes a bit due to the fact that if length of range is even, then you have to do the same for this sequence
… L+1, L+3, L+5… R
Else do this for
… L+1, L+3,L+5…R-1
Now the gaps are like :
0 0 0
0 1 0
1 0 0
1 1 0
Or
0 0 1
0 1 1
1 0 1
So formula is different for different cases but derived in same manner, by grouping 2^i numbers and then counting the remaining.

Sure,
to derive formula for sequence what I did was for bit i I saw a pattern )in sequence or case :
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
We see that i th (1 based indexing) bit follows sequence of 0s and 1s with a period of 2^(i-1) and in each period they occur equally, so I found first number of such periods. That is given by floor ((x+1) /(2^(i-1))).
Theb multiply these periods by 2^(i-2) to get total ones in those periods.
Now for the remaining part which is (x+1) mod(2^(i-1)) we find if it is greater than 2^(i-2)(because period starts with zeros) then we count the difference between mod and this threshold as the remaining number of uncounted ones. Otherwise there isn’t any remaining number of ones. With counted ones it’s trivial to find answer via addition of each bit on the basis of parity.

I think I can elaborate in simple words.
Firstly the upper limits of both L and R is in range of 10^15 , which hints it might be a pattern finding problem.

below is index , binary & values of XOR[i] where i is from 0 to 32

Index

Binary

Value

0

000000

0

1

000001

1

2

000011

3

3

000000

0

4

000100

4

5

000001

1

6

000111

7

7

000000

0

8

001000

8

9

000001

1

10

001011

11

11

000000

0

12

001100

12

13

000001

1

14

001111

15

15

000000

0

16

010000

16

17

000001

1

18

010011

19

19

000000

0

20

010100

20

21

000001

1

22

010111

23

23

000000

0

24

011000

24

25

000001

1

26

011011

27

27

000000

0

28

011100

28

29

000001

1

30

011111

31

31

000000

0

32

100000

32

We can make 2 important deductions from this

There is 0 at 3 , 7 , 11 , 15 , 19… i.e at 4n-1th term ( where n starts from 1 )

XOR of range of every 4 elements is 2. i.e. XOR(0 , 3) = 2 , XOR(4,7) = 2 , XOR(8,11) = 2

Hence using above two deductions we our required range XOR.

// FIRST
let input = [2, 4]
const arr = [0]
for (let num= 1; num<= input[1]; num++) {
arr.push(arr[arr.length-1] ^ num)
}
console.log(arr.slice(input[0], ++input[1]).reduce((prev, curr) => prev ^ curr)) // 7 --- will give run time error for huge input number
--------------------------------------------------------------------------------------------------------------------------------------------
// SECOND
function computeXOR (n) {
switch (n & 3) {
case 0:
return n
case 1:
return 1
case 2:
return n + 1
default:
return 0
}
}
let input2 = [2, 4]
let start = computeXOR(input2[0])
let i = input2[0]
let next = start
while (i < input2[1]) {
start = start ^ ++i
next = next ^ start
}
console.log(next) // 7