0% completed
Problem Statement
You are given an array arr
containing integers greater than 0
. Additionally, you are given the array of queries where queries[i] = [left<sub>i</sub>, right<sub>i</sub>].
For each query, compute the XOR of the elements in arr
from index left<sub>i</sub> to right<sub>i</sub> (inclusive)
Return an array answer
where answer[i]
represents the result of the i<sup>th</sup> query.
Examples
Example 1:
- Input: arr =
[2, 4, 7, 3]
, queries =[[0, 1], [1, 3], [0, 2]]
- Expected Output:
[6, 0, 1]
- Explanation:
- For the first query [0, 1], XOR of elements from index 0 to 1: 2 XOR 4 = 6
- For the second query [1, 3], XOR of elements from index 1 to 3: 4 XOR 7 XOR 3 = 0
- For the third query [0, 2], XOR of elements from index 0 to 2: 2 XOR 4 XOR 7 = 1
Example 2:
- Input: arr =
[5, 9, 12, 6]
, queries =[[2, 3], [0, 2], [1, 2]]
- Expected Output:
[10, 0, 5]
- Explanation:
- For the first query [2, 3], XOR of elements from index 2 to 3: 12 XOR 6 = 10
- For the second query [0, 2], XOR of elements from index 0 to 2: 5 XOR 9 XOR 12 = 0
- For the third query [1, 2], XOR of elements from index 1 to 2: 9 XOR 12 = 5
Example 3:
- Input: arr =
[1, 3, 5, 7, 9]
, queries =[[1, 4], [0, 3], [2, 4]]
- Expected Output:
[8, 0, 11]
- Explanation:
- For the first query [1, 4], XOR of elements from index 1 to 4: 3 XOR 5 XOR 7 XOR 9 = 8
- For the second query [0, 3], XOR of elements from index 0 to 3: 1 XOR 3 XOR 5 XOR 7 = 0
- For the third query [2, 4], XOR of elements from index 2 to 4: 5 XOR 7 XOR 9 = 11
Constraints:
- 1 <= arr.length, queries.length <= 3 * 10<sup>4</sup>
- 1 <= arr[i] <= 10<sup>9</sup>
- queries[i].length == 2
- 0 <= left<sub>i</sub> <= right<sub>i</sub> < arr.length
Solution
To solve this problem, we can use Mo's Algorithm, which is a powerful technique used to answer multiple queries on an array in an efficient manner. The core idea is to sort the queries in a way that minimizes the amount of work needed to process them. We can do this by sorting based on the blocks of the query ranges and then processing each block while keeping track of the current XOR value. By moving the pointers to include or exclude elements in the current range, we can quickly compute the XOR for each query without recalculating from scratch.
This approach is effective because it reduces the time complexity compared to a naive approach where we would recompute the XOR for every query from scratch. By reusing the results from previous computations, we can answer each query in sub-linear time relative to the size of the array, making the algorithm scalable even for large inputs.
Step-by-Step Algorithm
-
Initialization:
- Define a class
Query
that stores each query'sleft
,right
indices and its original index in thequeries
array. This is essential for keeping track of the order of queries after sorting. - Initialize
blockSize
as the square root of the length ofarr
. - Create an array
qs[]
to store the queries asQuery
objects, with each query’sleft
,right
, and original index.
- Define a class
-
Sort Queries:
- Sort the queries in
qs[]
based on:- Block index calculated by
left / blockSize
. - If two queries have the same block index, sort by
right
index.
- Block index calculated by
- This ordering minimizes the movement of
currentLeft
andcurrentRight
pointers during query processing.
- Sort the queries in
-
Initialize Pointers:
- Set
currentLeft
to 0,currentRight
to -1, andcurrentXor
to 0. - These pointers track the current segment of
arr[]
being processed, andcurrentXor
stores the XOR of this segment.
- Set
-
Process Each Query:
- For each query in the sorted
qs[]
:- Expand
currentRight
: WhilecurrentRight
is less thanquery.right
, movecurrentRight
to the right, including new elements in the XOR calculation. - Shrink
currentRight
: WhilecurrentRight
is greater thanquery.right
, movecurrentRight
to the left, excluding elements from the XOR calculation. - Expand
currentLeft
: WhilecurrentLeft
is less thanquery.left
, movecurrentLeft
to the right, excluding elements from the XOR calculation. - Shrink
currentLeft
: WhilecurrentLeft
is greater thanquery.left
, movecurrentLeft
to the left, including new elements in the XOR calculation.
- Expand
- After adjusting
currentLeft
andcurrentRight
, store the computedcurrentXor
inanswer[query.index]
.
- For each query in the sorted
-
Return the Results:
- Once all queries are processed, return the
answer[]
array containing the results for each query.
- Once all queries are processed, return the
Algorithm Walkthrough
Let’s walk through the algorithm with arr = [2, 4, 7, 3]
and queries = [[0, 1], [1, 3], [0, 2]]
.
Step 1: Initialization
queries = [[0, 1], [1, 3], [0, 2]]
blockSize = 2
(sincesqrt(4) = 2
)answer[] = [0, 0, 0]
Step 2: Create Query
objects
qs[0] = Query(0, 1, 0)
→ corresponds to the first query.qs[1] = Query(1, 3, 1)
→ corresponds to the second query.qs[2] = Query(0, 2, 2)
→ corresponds to the third query.
Step 3: Sort the queries (qs[]
array)
- Here,
blockSize = 2
. All queries belong to the first block. The sorted Queries are:qs[0] = Query(0, 1, 0)
qs[1] = Query(0, 2, 2)
qs[2] = Query(1, 3, 1)
Step 4: Initialize pointers and currentXor
currentLeft = 0
currentRight = -1
currentXor = 0
Step 5: Process the first query (Query(0, 1, 0))
- Expand
currentRight
to 1:currentRight = 0
,currentXor = 0 XOR arr[0] = 0 XOR 2 = 2
currentRight = 1
,currentXor = 2 XOR arr[1] = 2 XOR 4 = 6
- No need to move
currentLeft
as it's already 0. - Store result:
answer[0] = 6
Step 6: Process the second query (Query(0, 2, 2))
- Expand
currentRight
to 2:currentRight = 2
,currentXor = 6 XOR arr[2] = 6 XOR 7 = 1
- No need to move
currentLeft
as it's already 0. - Store result:
answer[2] = 1
Step 7: Process the third query (Query(1, 3, 1))
- Expand
currentRight
to 3:currentRight = 3
,currentXor = 1 XOR arr[3] = 1 XOR 3 = 2
- Move
currentLeft
to 1:currentXor = 2 XOR arr[0] = 2 XOR 2 = 0
- Store result:
answer[1] = 0
Final Output:
answer[] = [6, 0, 1]
Code
Complexity Analysis
Time Complexity
The overall time complexity is O(Q \log Q + (N + Q) \times \sqrt{N}) \approx ((N + Q) \times \sqrt{N})), according to Mo's algorithm.
Space Complexity
- Space for Results: Storing the results for each query takes (Q) space.
- Auxiliary Space: The array and auxiliary data structures require O(N) space.
Overall Space Complexity: O(N + Q)
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible