Xor Queries Of A Subarray - Leetcode Solution

Problem:

You are given an array, nums, of n integers. You are also given q queries, where each query consists of a pair of indices l and r (0-indexed). For each query, compute the bitwise XOR of all the elements in the subarray nums[l, r] and return an array containing the results of all the queries.

Example 1:

Input: nums = [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

Solution:

Approach 1:

One approach is to solve the problem is to calculate the xor of sub-array of element from start to end and store the result in array. For ith query the answer would be arr[r[i]] xor arr[l[i] - 1].

The overall time complexity of this approach would be O(n*q). As for q queries we are traversing the array from start to end every time.

Approach 2:

A more efficient approach is discussed below. Make a prefix of xor and store it in an array xor_prefix. After that we can calculate the result for queries by the following formula:

arr[r[i]] xor arr[l[i] - 1]

This formula can be converted to:

xor_prefix[r[i]] xor xor_prefix[l[i] - 1]

The above two approaches are equivalent but we try to optimize the time complexity in the second approach to O(n+q).

Explanation:

Let's take an example

Nums = [1,3,4,8] Queries = [[0,1],[1,2],[0,3],[3,3]]

Initialize a prefix_xor array with first element as 0 i.e., prefix_xor[0] = 0.

    index  0   1    2   3
nums    1   3    4   8
prefix_xor 0   1    2   6 (initialize prefix_xor[0] = 0)

Now, prefix_xor[1] = nums[0] xor nums[1] = 1 xor 3 = 2 and so on.

After building the prefix array, the algorithm simply takes the xor of the subarray from prefix[l] to prefix[r] for each query.

Let's take the first query [0,1].

prefix_xor[1] xor prefix_xor[0] = 2 xor 0 = 2.

Similarly, the output of all the queries can be obtained.

The final solution is given below:

Complexity Analysis:

• Time Complexity : O(n + q), as we are visiting the array only once and for each query calculating the right answer.
• Space Complexity: O(n), as we are storing the prefix sums in the array of size n.

Solution in Python:

class Solution: def xorQueries(self, nums: List[int], queries: List[List[int]]) -> List[int]: n = len(nums) prefix_xor = [0]*n prefix_xor[0] = nums[0] for i in range(1,n): prefix_xor[i] = prefix_xor[i-1]^nums[i] result = [] for i in queries: result.append(prefix_xor[i[1]]^prefix_xor[i[0]-1] if i[0]>0 else prefix_xor[i[1]]) return result

Solution in Java:

class Solution { public int[] xorQueries(int[] nums, int[][] queries) { int n = nums.length; int[] prefix_xor = new int[n]; prefix_xor[0] = nums[0]; for(int i = 1;i < n;i++){ prefix_xor[i] = prefix_xor[i-1]^nums[i]; } int result[] = new int[queries.length]; for(int i = 0;i < queries.length;i++){ int l = queries[i][0]; int r = queries[i][1]; result[i] = prefix_xor[r] ^ (l > 0 ? prefix_xor[l-1] : 0); } return result; } }

1