Skip to content

Intuition

The problem asks for the XOR of elements between two indices for each query. Calculating the XOR for each query from scratch would be inefficient, especially when there are multiple queries. The idea is to use a prefix XOR array to store the XOR of elements from the start of the array to any index. This allows us to compute the XOR of any subarray in constant time.

Approach

  1. Prefix XOR Array:
  2. Construct a prefix XOR array where each element at index i represents the XOR of all elements from the start of the array to index i-1.
  3. Using the prefix XOR array, the XOR of a subarray between indices start and end can be computed as: XOR(arr[start..end]) = prefixXor[end+1] ⊕ prefixXor[start]

  4. This allows each query to be processed in O(1) time.

  5. Query Processing:

  6. For each query, extract the start and end indices, and use the prefix XOR array to quickly compute the XOR for the subarray.

Complexity

  • Time complexity: Building the prefix XOR array takes O(n), where n is the size of the input array.
  • Each query is processed in O(1), so for m queries, the total time for query processing is O(m).

  • Therefore, the overall time complexity is O(n + m).

  • Space complexity: We use an additional array prefixXor of size n+1 to store the XOR of elements up to each index, so the space complexity is O(n).

Code

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

        for (int i = 1; i <= n; i++) {
            prefixXor[i] = prefixXor[i - 1] ^ arr[i - 1];
        }

        for (int i = 0; i < queries.length; i++) {
            int start = queries[i][0];
            int end = queries[i][1];
            result[i] = prefixXor[end + 1] ^ prefixXor[start];
        }

        return result;
    }
}