Problem

You are given an array nums of n integers, and a 2D integer array queries of size q, where queries[i] = [li, ri].

For each query, you must find the maximum XOR score of any subarray of nums[li..ri].

The XOR score of an array a is found by repeatedly applying the following operations on a so that only one element remains, that is the score :

  • Simultaneously replace a[i] with a[i] XOR a[i + 1] for all indices i except the last one.
  • Remove the last element of a.

Return an array answer of size q where answer[i] is the answer to query i.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


Input: nums = [2,8,4,32,16,1], queries = [[0,2],[1,4],[0,5]]

Output: [12,60,60]

Explanation:

In the first query, `nums[0..2]` has 6 subarrays `[2]`, `[8]`, `[4]`, `[2,
8]`, `[8, 4]`, and `[2, 8, 4]` each with a respective XOR score of 2, 8, 4,
10, 12, and 6. The answer for the query is 12, the largest of all XOR scores.

In the second query, the subarray of `nums[1..4]` with the largest XOR score
is `nums[1..4]` with a score of 60.

In the third query, the subarray of `nums[0..5]` with the largest XOR score is
`nums[1..4]` with a score of 60.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


Input: nums = [0,7,3,2,8,5,1], queries = [[0,3],[1,5],[2,4],[2,6],[5,6]]

Output: [7,14,11,14,5]

Explanation:

Index | nums[li..ri] | Maximum XOR Score Subarray | Maximum Subarray XOR Score  
---|---|---|---  
0 | [0, 7, 3, 2] | [7] | 7  
1 | [7, 3, 2, 8, 5] | [7, 3, 2, 8] | 14  
2 | [3, 2, 8] | [3, 2, 8] | 11  
3 | [3, 2, 8, 5, 1] | [2, 8, 5, 1] | 14  
4 | [5, 1] | [5] | 5

Constraints

  • 1 <= n == nums.length <= 2000
  • 0 <= nums[i] <= 2^31 - 1
  • 1 <= q == queries.length <= 10^5
  • queries[i].length == 2
  • queries[i] = [li, ri]
  • 0 <= li <= ri <= n - 1

Solution

Method 1 – Prefix XOR and Brute Force

Intuition

The XOR score of a subarray is the XOR of all its elements. For each query, we need the maximum XOR of any subarray within the given range. We can use prefix XORs to compute the XOR of any subarray efficiently, and then check all possible subarrays in the range.

Approach

  1. Precompute prefix XORs for the array.
  2. For each query [l, r], iterate over all possible subarrays in nums[l..r].
  3. For each subarray, compute its XOR using prefix XORs.
  4. Track the maximum XOR score for each query.
  5. Return the results for all queries.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    vector<int> maximumXorScoreSubarrayQueries(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> pre(n + 1, 0);
        for (int i = 0; i < n; ++i) pre[i + 1] = pre[i] ^ nums[i];
        vector<int> ans;
        for (auto& q : queries) {
            int l = q[0], r = q[1], mx = 0;
            for (int i = l; i <= r; ++i) {
                for (int j = i; j <= r; ++j) {
                    int cur = pre[j + 1] ^ pre[i];
                    if (cur > mx) mx = cur;
                }
            }
            ans.push_back(mx);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func maximumXorScoreSubarrayQueries(nums []int, queries [][]int) []int {
    n := len(nums)
    pre := make([]int, n+1)
    for i := 0; i < n; i++ {
        pre[i+1] = pre[i] ^ nums[i]
    }
    ans := make([]int, len(queries))
    for idx, q := range queries {
        l, r := q[0], q[1]
        mx := 0
        for i := l; i <= r; i++ {
            for j := i; j <= r; j++ {
                cur := pre[j+1] ^ pre[i]
                if cur > mx {
                    mx = cur
                }
            }
        }
        ans[idx] = mx
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int[] maximumXorScoreSubarrayQueries(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] pre = new int[n + 1];
        for (int i = 0; i < n; i++) pre[i + 1] = pre[i] ^ nums[i];
        int[] ans = new int[queries.length];
        for (int k = 0; k < queries.length; k++) {
            int l = queries[k][0], r = queries[k][1], mx = 0;
            for (int i = l; i <= r; i++) {
                for (int j = i; j <= r; j++) {
                    int cur = pre[j + 1] ^ pre[i];
                    if (cur > mx) mx = cur;
                }
            }
            ans[k] = mx;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun maximumXorScoreSubarrayQueries(nums: IntArray, queries: Array<IntArray>): IntArray {
        val n = nums.size
        val pre = IntArray(n + 1)
        for (i in 0 until n) pre[i + 1] = pre[i] xor nums[i]
        val ans = IntArray(queries.size)
        for (k in queries.indices) {
            val l = queries[k][0]
            val r = queries[k][1]
            var mx = 0
            for (i in l..r) {
                for (j in i..r) {
                    val cur = pre[j + 1] xor pre[i]
                    if (cur > mx) mx = cur
                }
            }
            ans[k] = mx
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def maximum_xor_score_subarray_queries(nums: list[int], queries: list[list[int]]) -> list[int]:
    n = len(nums)
    pre = [0] * (n + 1)
    for i in range(n):
        pre[i + 1] = pre[i] ^ nums[i]
    ans = []
    for l, r in queries:
        mx = 0
        for i in range(l, r + 1):
            for j in range(i, r + 1):
                cur = pre[j + 1] ^ pre[i]
                if cur > mx:
                    mx = cur
        ans.append(mx)
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
    pub fn maximum_xor_score_subarray_queries(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
        let n = nums.len();
        let mut pre = vec![0; n + 1];
        for i in 0..n {
            pre[i + 1] = pre[i] ^ nums[i];
        }
        let mut ans = Vec::new();
        for q in queries.iter() {
            let l = q[0] as usize;
            let r = q[1] as usize;
            let mut mx = 0;
            for i in l..=r {
                for j in i..=r {
                    let cur = pre[j + 1] ^ pre[i];
                    if cur > mx { mx = cur; }
                }
            }
            ans.push(mx);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    maximumXorScoreSubarrayQueries(nums: number[], queries: number[][]): number[] {
        const n = nums.length;
        const pre = new Array(n + 1).fill(0);
        for (let i = 0; i < n; ++i) pre[i + 1] = pre[i] ^ nums[i];
        const ans: number[] = [];
        for (const [l, r] of queries) {
            let mx = 0;
            for (let i = l; i <= r; ++i) {
                for (let j = i; j <= r; ++j) {
                    const cur = pre[j + 1] ^ pre[i];
                    if (cur > mx) mx = cur;
                }
            }
            ans.push(mx);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(q * n^2), for each query, we check all subarrays in the range.
  • 🧺 Space complexity: O(n), for prefix XORs.