# 9. XOR Queries of a Subarray

Given the array `arr` of positive integers and the array `queries` where `queries[i] = [Li, Ri]`, for each query `i` compute the **XOR** of elements from `Li` to `Ri` (that is, `arr[Li]`` `**`xor`**` ``arr[Li+1]`` `**`xor`**` ``...`` `**`xor`**` ``arr[Ri]` ). Return an array containing the result for the given `queries`.

**Example 1:**

```
Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
Output: [2,7,14,8] 
Explanation: 
The binary representation of the elements in the array are:
1 = 0001 
3 = 0011 
4 = 0100 
8 = 1000 
The XOR values for queries are:
[0,1] = 1 xor 3 = 2 
[1,2] = 3 xor 4 = 7 
[0,3] = 1 xor 3 xor 4 xor 8 = 14 
[3,3] = 8
```

**Example 2:**

```
Input: arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
Output: [8,0,4,4]
```

#### Approach:(V.IMP)

> **The XOR trick: If we have a sequence of XOR operations `a ^ b ^ c ^ ...`, then we can remove all pairs of duplicated values without affecting the result.**

Commutativity allows us to re-order the applications of XOR so that the duplicated elements are next to each other. Since `x ^ x = 0` and `a ^ 0 = a`, each pair of duplicated values has no effect on the outcome.

Let’s go through an example of this:

```
  a ^ b ^ c ^ a ^ b     # Commutativity
= a ^ a ^ b ^ b ^ c     # Using x ^ x = 0
= 0 ^ 0 ^ c             # Using x ^ 0 = x (and commutativity)
= c
```

## Solution: 

```cpp
class Solution
{
public:
    vector<int> xorQueries(vector<int> &arr, vector<vector<int>> &queries)
    {

        vector<int> res;
        for (int i = 1; i < arr.size(); i++)
        {
            arr[i] = arr[i] ^ arr[i - 1];
        }

        for (int i = 0; i < queries.size(); i++)
        {
            int start = queries[i][0];
            int end = queries[i][1];
            int ans;
            if (start != 0)
            {
                ans = arr[end] ^ arr[start - 1];
            }
            else
            {
                ans = arr[end];
            }

            res.push_back(ans);
        }

        return res;
    }
};
```

**Time Complexity: O(n)**


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://soumyajit4419.gitbook.io/ds-algo/maths/10.-xor-queries-of-a-subarray.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.