Xor query Problem

help
1

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

2

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.

3 Likes
3

not understood !! can u give some example it might help me

4

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.

5

but the pattern/series is
0 0 0 0
0 0 0 1
0 0 1 1
0 0 0 0
0 1 0 0
0 0 0 1
0 1 1 1
0 0 0 0

6

Bro the numbers are at the gap of 2, so I do not think this is the correct pattern.

7

dude
relation is
A[i]=0 for i=0
A[i]=A[i-1] xor i (for i>1)

8

AL xor AL+1 xor AL+2 xor … AR = L+1 xor L+3 xor L+5 … because Ai+1 = Ai xor (i+1).
I hope you got it!
Feel free to point out any mistake or doubt!:smile:

9

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

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

  2. 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.

eg. L = 2 R = 16

we know that, XOR (4,7) = (8,11) = (12,15) = 2
Therefore 2 ^ 2 ^2 = 2

if number of twos in given range is even, then their XOR wil be 0 , else XOR will be 2

now using 1st property can find XOR(2,4).
now using the total result, go XORING till R = 16 to get final answer.

If you understood till 2 deductions, you can use any approach to apply that.

2 Likes
10 
// 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