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 * 1041 <= arr[i] <= 109queries[i].length == 20 <= lefti <= righti < arr.length
Solutions#
Solution 1#
1
2
3
4
| 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]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
| 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| function xorQueries(arr: number[], queries: number[][]): number[] {
const n = arr.length;
const s: number[] = new Array(n + 1).fill(0);
for (let i = 0; i < n; ++i) {
s[i + 1] = s[i] ^ arr[i];
}
const ans: number[] = [];
for (const [l, r] of queries) {
ans.push(s[r + 1] ^ s[l]);
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| /**
* @param {number[]} arr
* @param {number[][]} queries
* @return {number[]}
*/
var xorQueries = function (arr, queries) {
const n = arr.length;
const s = new Array(n + 1).fill(0);
for (let i = 0; i < n; ++i) {
s[i + 1] = s[i] ^ arr[i];
}
const ans = [];
for (const [l, r] of queries) {
ans.push(s[r + 1] ^ s[l]);
}
return ans;
};
|
