LeetCode 1310. XOR Queries of a Subarray Solution in Java, C++, Python & More | Explanation + Code

Description

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

Solutions

Solution 1: Prefix XOR

We can use a prefix XOR array s of length n+1 to store the prefix XOR results of the array arr, where s[i] = s[i-1] \oplus arr[i-1]. That is, s[i] represents the XOR result of the first i elements of arr.

For a query [l, r], we can obtain:

\begin{aligned} arr[l] \oplus arr[l+1] \oplus … \oplus arr[r] &= (arr[0] \oplus arr[1] \oplus … \oplus arr[l-1]) \oplus (arr[0] \oplus arr[1] \oplus … \oplus arr[r]) \ &= s[l] \oplus s[r+1] \end{aligned}

Time complexity is O(n+m), and space complexity is O(n). Here, n and m are the lengths of the array arr and the query array queries, respectively.

PythonJavaC++GoTypeScriptJavaScript

class Solution: def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]: s = list(accumulate(arr, xor, initial=0)) return [s[r + 1] ^ s[l] for l, r in queries](code-box)

class Solution { public int[] xorQueries(int[] arr, int[][] queries) { int n = arr.length; int[] s = new int[n + 1]; for (int i = 1; i <= n; ++i) { s[i] = s[i - 1] ^ arr[i - 1]; } int m = queries.length; int[] ans = new int[m]; for (int i = 0; i < m; ++i) { int l = queries[i][0], r = queries[i][1]; ans[i] = s[r + 1] ^ s[l]; } return ans; } }(code-box)

class Solution { public: vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) { int n = arr.size(); int s[n + 1]; memset(s, 0, sizeof(s)); for (int i = 1; i <= n; ++i) { s[i] = s[i - 1] ^ arr[i - 1]; } vector<int> ans; for (auto& q : queries) { int l = q[0], r = q[1]; ans.push_back(s[r + 1] ^ s[l]); } return ans; } };(code-box)

func xorQueries(arr []int, queries [][]int) (ans []int) { n := len(arr) s := make([]int, n+1) for i, x := range arr { s[i+1] = s[i] ^ x } for _, q := range queries { l, r := q[0], q[1] ans = append(ans, s[r+1]^s[l]) } return }(code-box)

function xorQueries(arr: number[], queries: number[][]): number[] { const n = arr.length; const s: number[] = Array(n + 1).fill(0); for (let i = 0; i < n; ++i) { s[i + 1] = s[i] ^ arr[i]; } return queries.map(([l, r]) => s[r + 1] ^ s[l]); }(code-box)

/** * @param {number[]} arr * @param {number[][]} queries * @return {number[]} */ var xorQueries = function (arr, queries) { const n = arr.length; const s = Array(n + 1).fill(0); for (let i = 0; i < n; ++i) { s[i + 1] = s[i] ^ arr[i]; } return queries.map(([l, r]) => s[r + 1] ^ s[l]); };(code-box)