LeetCode Entry
1310. XOR Queries of a Subarray
Run queries[[from, to]] of xor(arr[from..to]) manipulation
1310. XOR Queries of a Subarray medium
blog post
substack
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/733
Problem TLDR
Run queries[[from, to]] of xor(arr[from..to]) #medium #bit_manipulation
Intuition
The xor operation is cumulative and associative: swapping and grouping don’t matter (like a sum or multiply). So, we can precompute prefix xor and use it to compute xor[i..j] in O(1).
Approach
- we can reuse the input array
Complexity
-
Time complexity: \(O(n)\)
-
Space complexity: \(O(n)\)
Code
fun xorQueries(arr: IntArray, queries: Array<IntArray>): IntArray {
for (i in 1..<arr.size) arr[i] = arr[i] xor arr[i - 1]
return queries.map { (from, to) ->
arr[to] xor (arr.getOrNull(from - 1) ?: 0)
}.toIntArray()
}
pub fn xor_queries(mut arr: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
for i in 1..arr.len() { arr[i] ^= arr[i - 1] }
queries.into_iter().map(|q|
arr[q[1] as usize] ^ arr[..].get(q[0] as usize - 1).unwrap_or(&0)).collect()
}
vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
for (int i = 1; i < arr.size(); i++) arr[i] ^= arr[i - 1];
vector<int> res; res.reserve(queries.size());
for (const auto q: queries)
res.push_back(arr[q[1]] ^ (q[0] > 0 ? arr[q[0] - 1] : 0));
return res;
}