XOR Queries of a Subarray — LeetCode 1310 Python Solution

The problem

You are given an array arr of positive integers. You are also given the array queries where queries[i] = [lefti, righti].

Example

Input

arr = [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:

Python solution

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        s = list(accumulate(arr, xor, initial=0))
        return [s[r + 1] ^ s[l] for l, r in queries]

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 1310. XOR Queries of a Subarray is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems