Maximum XOR for Each Query

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 ... XOR nums[nums.length-1] XOR k is maximized. k is the answer to the ith query.
Remove the last element from the current array nums.

Return an array answer, where answer[i] is the answer to the ith query.

Examples

Example 1:

Input: nums = [0,1,1,3], maximumBit = 2
Output: [0,3,2,3]
Explanation: The queries are answered as follows:
1st query: nums = [0,1,1,3], k = 0 since 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3.
2nd query: nums = [0,1,1], k = 3 since 0 XOR 1 XOR 1 XOR 3 = 3.
3rd query: nums = [0,1], k = 2 since 0 XOR 1 XOR 2 = 3.
4th query: nums = [0], k = 3 since 0 XOR 3 = 3.

Example 2:

Input: nums = [2,3,4,7], maximumBit = 3
Output: [5,2,6,5]
Explanation: The queries are answered as follows:
1st query: nums = [2,3,4,7], k = 5 since 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7.
2nd query: nums = [2,3,4], k = 2 since 2 XOR 3 XOR 4 XOR 2 = 7.
3rd query: nums = [2,3], k = 6 since 2 XOR 3 XOR 6 = 7.
4th query: nums = [2], k = 5 since 2 XOR 5 = 7.

Example 3:

Input: nums = [0,1,2,2,5,7], maximumBit = 3
Output: [4,3,6,4,6,7]

Constraints

0 <= nums[i] < 2^maximumBit

Solution

Method 1 - Calculate xor of whole array

The goal is to find the value of k such that the XOR of all elements in nums and k is maximized for each query. We are given that k < 2^maximumBit, so maximum possible value is achieved with (1 << maximumBit) - 1, meaning all bits within the maximumBit range are set.

It's important to note this constraint as well:

0 <= nums[i] < 2^maximumBit

Why is the maximum always 2^maximumBit - 1? Given that each element in nums lies within the range [0, 2^maximumBit - 1], after XOR-ing all elements, the resulting value (let's call it numsXor) will also be within this range. Because at maximum, this value will be equal to 2 ^ maxBit - 1.

To maximize the resultant numsXor output, we can xor this value with any number within [0, 2^maximumBit - 1]. The optimal choice is the number which, when XOR-ed with numsXor, yields 2^maximumBit - 1.

For maximumBit = 3, the range is [0, 7]. To achieve the maximum result when XOR-ing number a with another number b, the other number must have opposite bits in each position to ensure all bits are set.

Consider:

maximumBit = 3
numsXor = 0 (000) can be maximized by XOR-ing with 7 to get 7.
    0 (000)
  ^ 7 (111)
  ----------
    7 (111)


numsXor = 1 (001) can be maximized by XOR-ing with 6 to get 7.
    1 (001)
  ^ 6 (110)
  ----------
    7 (111)

numsXor = 2 (010) can be maximized by XOR-ing with 5 to get 7.
    2 (010)
  ^ 5 (101)
  ----------
    7 (111)

numsXor = 3 (011) can be maximized by XOR-ing with 4 to get 7.
    3 (011)
  ^ 4 (100)
  ----------
    7 (111)

numsXor = 4 (100) can be maximized by XOR-ing with 3 to get 7.
    4 (100)
  ^ 3 (011)
  ----------
    7 (111)

and so on.

Following this logic, we can always choose a number to maximize XOR to 2^maximumBit - 1. After computing numsXor for the original nums array, subsequent changes involve removing the last element. We update numsXor by XOR-ing it with the removed element, leveraging the property that XOR-ing an element twice cancels it out. This gives the final answer for each query.

The general idea is:

Calculate the XOR of all elements in the array nums initially, let’s call it nums_xor.
For each query, calculate the best possible value of k that, when XORed with nums_xor, provides the maximum value. Since we want the result to be the maximum, k should be nums_xor XOR with all bits set to 1 within the range 2^maximumBit - 1 (this is 2^maximumBit - 1).
Remove the last element of the array nums and update nums_xor by XORing it with the removed element.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

Java

class Solution {
    public int[] getMaximumXor(int[] nums, int maximumBit) {        
        int numsXor = 0;
        for (int num : nums) {
            numsXor ^= num;
        }
        
        int n = nums.length;
        int[] ans = new int[n];
        int maxK = (1 << maximumBit) - 1;
        
        for (int i = 0; i < n; i++) {
            ans[i] = numsXor ^ maxK;
            numsXor ^= nums[n - 1 - i];
        }
        return ans;
    }
}

Python

class Solution:
    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
        nums_xor = 0
        for num in nums:
            nums_xor ^= num
        
        n = len(nums)
        ans = [0] * n
        max_k = (1 << maximumBit) - 1
        
        for i in range(n):
            ans[i] = nums_xor ^ max_k
            nums_xor ^= nums[n - 1 - i]
        
        return ans

Complexity

⏰ Time complexity: O(n) where n is the number of elements in nums because we are iterating through the list once and performing constant time operations.
🧺 Space complexity: O(1) additional space for calculation, not counting the space of the output array.