XOR Queries of a Subarray

Share

Given an array arr and queries where queries[i] = [left, right], return the XOR of elements from arr[left] to arr[right] for each query.

Example 1
Input: arr=[1,3,4,8], queries=[[0,1],[1,2],[0,3],[3,3]] → Output: [2,7,14,8]
Example 2
Input: arr=[4,8,2,10], queries=[[2,3],[1,3],[0,0],[0,3]] → Output: [8,0,4,4]

Solution Approach

Precompute prefix XOR array where prefix[i] = arr[0] XOR arr[1] XOR ... XOR arr[i-1]. Then XOR of arr[l..r] = prefix[r+1] XOR prefix[l].

  • Build prefix XOR: prefix[0]=0, prefix[i]=prefix[i-1]^arr[i-1].
  • For each query [l, r]: answer = prefix[r+1] ^ prefix[l].
  • This works because a^a=0, so all elements before index l cancel out.
Java
class Solution {
    public int[] xorQueries(int[] arr, int[][] queries) {
        int n = arr.length;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] ^ arr[i];
        int[] result = new int[queries.length];
        for (int i = 0; i < queries.length; i++)
            result[i] = prefix[queries[i][1] + 1] ^ prefix[queries[i][0]];
        return result;
    }
}
  • Time Complexity: O(N + Q)
  • Space Complexity: O(N) for prefix array