Maximum XOR for Each Query — LeetCode 1829 Python Solution

The problem

You are given a sorted array nums of n non-negative integers and an integer maximumBit. You want to perform the following query n times: Find a non-negative integer k < 2maximumBit such that nums[0] XOR nums[1] XOR ...

Example

Input

nums = [0,1,1,3], maximumBit = 2

Output

[0,3,2,3]

Explanation

The queries are answered as follows:

Python solution

class Solution:
    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
        ans = []
        xs = reduce(xor, nums)
        for x in nums[::-1]:
            k = 0
            for i in range(maximumBit - 1, -1, -1):
                if (xs >> i & 1) == 0:
                    k |= 1 << i
            ans.append(k)
            xs ^= x
        return ans

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 1829. Maximum XOR for Each Query 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