XOR Queries of Subarray

Moderate

0/80

Contributed by

3 upvotes

Asked in company

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
5
1 3 4 3 5
3
0 3
1 4
2 3
8
7 4 5 2 6 3 8 1
1
2 5

Sample Output 1 :

5 1 7
2

Explanation For Sample Input 1 :

For test case 1 : 
Given array is { 1, 3, 4, 3, 5 }
query 1: 1 ^ 3 ^ 4 ^ 3 = 5
query 2: 3 ^ 4 ^ 3 ^ 5 = 1
query 3: 4 ^ 3 = 7

For test case 2 :
Given array is { 7, 4, 5, 2, 6, 3, 8, 1 }
query 1: 5 ^ 2 ^ 6 ^ 3 = 2

Sample Input 2 :

Sample Output 2 :

100
14 4

Hint 1

Hint 2

Can you take advantage of the small constraints?

Approaches (2)

Approach 1

Approach 2

Brute Force

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 L^th to R^th 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.

Time Complexity

O( N * Q ), where N and Q denote the size of the array and the number of queries respectively.

For each query in the worst case, we might have to iterate all the array elements to compute the XOR of the subarray.

Hence the time complexity is O( N * Q ).

Space Complexity

O( 1 )

No extra space is used. Hence the space complexity is O(1).

(100% EXP penalty)

XOR Queries of Subarray

Console