1310. XOR Queries of a Subarray LeetCode Solution

In this guide, you will get 1310. XOR Queries of a Subarray LeetCode Solution with the best time and space complexity. The solution to XOR Queries of a Subarray problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
XOR Queries of a Subarray solution in C++
XOR Queries of a Subarray solution in Java
XOR Queries of a Subarray solution in Python
Additional Resources

1310. XOR Queries of a Subarray LeetCode Solution image

Problem Statement of XOR Queries of a Subarray

You are given an array arr of positive integers. You are also given the array queries where queries[i] = [lefti, righti].
For each query i compute the XOR of elements from lefti to righti (that is, arr[lefti] XOR arr[lefti + 1] XOR … XOR arr[righti] ).
Return an array answer where answer[i] is the answer to the ith query.

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]

Constraints:

1 <= arr.length, queries.length <= 3 * 104
1 <= arr[i] <= 109
queries[i].length == 2
0 <= lefti <= righti < arr.length

Complexity Analysis

Time Complexity:
Space Complexity:

1310. XOR Queries of a Subarray LeetCode Solution in C++

class Solution {
 public:
  vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
    vector<int> ans;
    vector<int> xors(arr.size() + 1);

    for (int i = 0; i < arr.size(); ++i)
      xors[i + 1] = xors[i] ^ arr[i];

    for (const vector<int>& query : queries) {
      const int left = query[0];
      const int right = query[1];
      ans.push_back(xors[left] ^ xors[right + 1]);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

1310. XOR Queries of a Subarray LeetCode Solution in Java

class Solution {
  public int[] xorQueries(int[] arr, int[][] queries) {
    int[] ans = new int[queries.length];
    int[] xors = new int[arr.length + 1];

    for (int i = 0; i < arr.length; ++i)
      xors[i + 1] = xors[i] ^ arr[i];

    int i = 0;
    for (int[] query : queries) {
      final int left = query[0];
      final int right = query[1];
      ans[i++] = xors[left] ^ xors[right + 1];
    }

    return ans;
  }
}
// code provided by PROGIEZ

1310. XOR Queries of a Subarray LeetCode Solution in Python

class Solution:
  def xorQueries(self, arr: list[int], queries: list[list[int]]) -> list[int]:
    ans = []
    xors = [0] * (len(arr) + 1)

    for i, a in enumerate(arr):
      xors[i + 1] = xors[i] ^ a

    for left, right in queries:
      ans.append(xors[left] ^ xors[right + 1])

    return ans
 # code by PROGIEZ