Last Updated: 29 Aug, 2021
XOR Queries of Subarray
Moderate
Asked in company
You are given an array ‘Arr’ containing ‘N’ positive integers.
You have to process ‘Q’ queries. In each query you are given two integers ‘L’ and ‘R’, compute the ‘XOR’ of elements in the subarray from L to R (inclusive), ie: compute the value Arr [ L ] ^ Arr [ L + 1 ] ^ Arr [ L + 2 ] ^ . . . . ^ Arr [ R ], where ‘ ^ ’ represents the XOR operator.
Example :
If N = 5 and the array is: { 1, 3, 4, 3, 5 }, and for the given query L = 0 and R = 3, then we will return 1 ^ 3 ^ 4 ^ 3 = 5.
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:
The first line of each test case contains a single integer ‘N’ denoting the size of the array.
The second line of each test case contains N positive integers denoting the array elements ‘Arr[i]’.
The third line of each test case contains a single integer ‘Q’ denoting the number of queries to be processed.
The next Q lines each contains two integers ‘L’ and ‘R’ denoting the start and end indexes of the subarray whose XOR needs to be computed.
Output Format :
For each test case, print Q integers, each denoting the subarray XOR for the given query.
Output for each test case will be printed in a separate line.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function and return an array that stores the answer to each query.
Constraints :
1 <= T <= 10
1 <= N <= 100
1 <= Arr[i] <= 10^5
1 <= Q <= 200
0 <= L <= R <= N-1
Time limit: 1 sec
Approaches
For each query simply run a loop and calculate the XOR of the subarray from L to R, after processing all the queries return the answer.
The steps are as follows :
- Initialize an array “ans” to store the answer to each query.
- Start processing each query, for each query simply run a loop from Lth to Rth index of the array and calculate the XOR of elements in that subarray.
- Insert the XOR computed into “ans” and process the next query.
- Finally, return “ans” when you have processed all the queries.
We can directly get the value of the XOR of the subarray from L to R if we know the XOR value of 0 to R and the XOR value of 0 to L - 1. This is because of the fact that (x ^ y) ^ x = (x ^ x) ^ y = 0 ^ y = y.
This means XOR( L …. R ) = XOR( 0 ….. R ) ^ XOR( 0…..L-1 )
We can directly get the value of XOR( 0 ….. R ) and XOR( 0…..L-1 ) if we pre-calculate the prefix array to store XOR of elements from 0 to i at the ith position in the prefix array.
The steps are as follows :
- Initialize an array “ans” to store the answer to each query.
- Create a prefix array “prefArr” to store the XOR up to ith element.
- Start processing each query, for each query if L is equal to 0 then the answer for the query is prefArr[R].
- If L is not equal to 0, then the answer is prefArr[R] ^ prefArr[L-1] (where ‘^’ represents the XOR operator).
- Finally, return “ans” when you have processed all the queries.
Similar problems