1310. XOR Queries of a Subarray

MediumView on LeetCode

Array Bit Manipulation Prefix Sum

Time: O(n + q)

Space: O(n)

Intuition

XOR has the property: XOR(l,r) = prefix[r] XOR prefix[l-1]. Precompute prefix XOR array for O(1) range queries.

Algorithm

1prefix[i] = arr[0] XOR ... XOR arr[i].
2XOR(l,r) = prefix[r] XOR prefix[l-1] (with prefix[-1]=0).

Common Pitfalls

•XOR is its own inverse: a XOR a = 0. prefix[r] XOR prefix[l-1] gives the range XOR.

1310.cs

// Approach: Build XOR prefix array; each query [l, r] is answered by prefix[l] ^ prefix[r+1].
// Time: O(n + q) Space: O(n)

public 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 j = 0;
        int[] ans = new int[queries.Length];
        foreach (int[] query in queries)
        {
            int left = query[0];
            int right = query[1];
            ans[j++] = prefix[left] ^ prefix[right + 1];
        }

        return ans;
    }
}

Was this solution helpful?