# Maximum XOR for Each Query
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-xor-for-each-query)
Canonical: https://scaleengineer.com/dsa/problems/maximum-xor-for-each-query
**Patterns:** [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## 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**:

1. 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.
2. Remove the **last** element from the current array `nums`.

Return _an array_ `answer`_, where_ `answer[i]` _is the answer to the_ `ith` _query_.

**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:**

* `nums.length == n`
* `1 <= n <= 105`
* `1 <= maximumBit <= 20`
* `0 <= nums[i] < 2maximumBit`
* `nums`​​​ is sorted in **ascending** order.

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem. For each of the `n` queries, we first calculate the XOR sum of all elements currently in the array. Then, we determine the value of `k` that would maximize the total XOR sum. This `k` is stored, and finally, the last element of the array is removed to set up for the next query. This entire process is repeated `n` times.
**Time:** O(n^2) - The outer loop runs `n` times for the `n` queries. The inner loop, which calculates the XOR sum, runs `n`, `n-1`, `n-2`, ..., `1` times. The total number of XOR operations is the sum of this arithmetic series, which is `n * (n+1) / 2`, resulting in a quadratic time complexity. · **Space:** O(n) - We use an `ArrayList` to store a copy of the numbers, which takes O(n) space. The `answer` array also requires O(n) space.
**Pros:** It is simple to understand and implement as it directly translates the problem description into code.; It's a good starting point for understanding the problem mechanics before moving to more optimized solutions.
**Cons:** The time complexity of O(n^2) is too slow for the given constraints (n <= 10^5), and this solution will likely result in a 'Time Limit Exceeded' error.; It performs a lot of redundant work by re-calculating the XOR sum from scratch in each of the n queries.
### Explanation
The core idea is to find a non-negative integer `k < 2^maximumBit` that maximizes the expression `(nums[0] XOR ... XOR nums[m-1]) XOR k`. The maximum possible value for an expression constrained to `maximumBit` bits is `2^maximumBit - 1`. Let's call this `max_val`. To achieve this maximum result, we need to have `(XOR of current nums) XOR k = max_val`. By applying XOR properties, we can solve for `k`: `k = max_val XOR (XOR of current nums)`. 

The brute-force algorithm implements this logic straightforwardly. It iterates `n` times, and in each iteration, it re-calculates the XOR sum of the shrinking array, computes `k`, and then removes the last element. Using a dynamic data structure like an `ArrayList` in Java makes the removal of the last element convenient.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] getMaximumXor(int[] nums, int maximumBit) {
        int n = nums.length;
        int[] answer = new int[n];
        List<Integer> currentNums = new ArrayList<>();
        for (int num : nums) {
            currentNums.add(num);
        }

        int maxVal = (1 << maximumBit) - 1;

        for (int i = 0; i < n; i++) {
            // 1. Calculate current XOR sum
            int currentXor = 0;
            for (int num : currentNums) {
                currentXor ^= num;
            }

            // 2. Find k
            int k = currentXor ^ maxVal;
            answer[i] = k;

            // 3. Remove the last element
            if (!currentNums.isEmpty()) {
                currentNums.remove(currentNums.size() - 1);
            }
        }

        return answer;
    }
}
```
### Algorithm
- 1. Initialize an `answer` array of size `n`.
- 2. Create a mutable `List` from the input `nums` array to facilitate element removal.
- 3. Calculate `max_val = (1 << maximumBit) - 1`. This represents the number with all `maximumBit` bits set to 1, which is the target for our maximization.
- 4. Loop `n` times, from `i = 0` to `n-1`, to simulate each query:
    - a. Initialize a variable `current_xor = 0`.
    - b. Iterate through all elements of the current list and compute their bitwise XOR sum, storing it in `current_xor`.
    - c. The value of `k` that maximizes the expression is `k = current_xor ^ max_val`.
    - d. Store this `k` in the results: `answer[i] = k`.
    - e. Remove the last element from the list to prepare for the next query.
- 5. Return the `answer` array.

## Optimized Prefix XOR Calculation
This approach significantly improves upon the brute-force method by avoiding the redundant calculation of the XOR sum in each query. We can maintain a `running_xor` sum. After each query, instead of re-calculating the sum for the smaller array, we can update the `running_xor` in constant time by XORing it with the element that was just removed. This reduces the overall time complexity from quadratic to linear.
**Time:** O(n) - There is an initial loop to calculate the total XOR sum, which takes O(n). The main loop for the queries also runs `n` times, with each step inside being an O(1) operation. Therefore, the total time complexity is O(n) + O(n) = O(n). · **Space:** O(n) - This is primarily for the output `answer` array. The auxiliary space used for variables like `running_xor` and `maxVal` is O(1).
**Pros:** Extremely efficient with a linear time complexity of O(n), which easily passes the given constraints.; This is the optimal solution in terms of time complexity as we must at least look at each element once.; Uses constant auxiliary space (if the output array is not counted).
**Cons:** It requires a bit more insight to realize that the XOR sum can be updated incrementally rather than recomputed.
### Explanation
The key optimization lies in understanding the properties of the XOR operation. If we have the XOR sum of an array, say `X`, and we remove the last element `y`, the new XOR sum is simply `X XOR y`. This is because `(a XOR y) XOR y = a`.

Based on this, the algorithm is as follows:
1.  First, we perform a single pass over the entire `nums` array to compute the initial `running_xor`. This sum corresponds to the state for the first query.
2.  We calculate `max_val = (1 << maximumBit) - 1`, which is our target for the maximization.
3.  We then loop `n` times. In each iteration `i`, we are answering the `i`-th query.
    - The answer `k` is found using the current `running_xor`: `k = running_xor ^ max_val`.
    - We store this `k` in our result array.
    - Then, we update `running_xor` for the next query (which will have one less element). We do this by XORing `running_xor` with the element that is conceptually removed, which is `nums[n - 1 - i]`.
This process allows us to find each `k` in O(1) time after an initial O(n) setup, leading to an efficient O(n) overall solution.

```java
class Solution {
    public int[] getMaximumXor(int[] nums, int maximumBit) {
        int n = nums.length;
        int[] answer = new int[n];
        
        int maxVal = (1 << maximumBit) - 1;
        
        // Calculate the initial XOR sum of the entire array
        int runningXor = 0;
        for (int num : nums) {
            runningXor ^= num;
        }
        
        // Process the queries from first to last
        for (int i = 0; i < n; i++) {
            // For the current state, find k. The current XOR sum is runningXor.
            answer[i] = runningXor ^ maxVal;
            
            // Update runningXor for the next query by removing the last element.
            // The last element of the current array is nums[n - 1 - i].
            runningXor ^= nums[n - 1 - i];
        }
        
        return answer;
    }
}
```
### Algorithm
- 1. Initialize an `answer` array of size `n`.
- 2. Calculate `max_val = (1 << maximumBit) - 1`.
- 3. Initialize a variable `running_xor = 0`.
- 4. Iterate through the `nums` array once to calculate the total XOR sum of all its elements and store it in `running_xor`.
- 5. Loop `n` times, from `i = 0` to `n-1`, to answer each query:
    - a. The XOR sum for the current query is `running_xor`. Calculate the required `k` as `k = running_xor ^ max_val`.
    - b. Store the result: `answer[i] = k`.
    - c. To prepare for the next query, update `running_xor` by removing the effect of the last element. The last element of the array for query `i` is `nums[n - 1 - i]`. Update the sum: `running_xor ^= nums[n - 1 - i]`.
- 6. Return the `answer` array.

# Solutions
### CSharp

```csharp
public class Solution {
    public int[] GetMaximumXor(int[] nums, int maximumBit) {
        int xs = 0;
        foreach(int x in nums) {
            xs ^= x;
        }
        int n = nums.Length;
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            int x = nums[n - i - 1];
            int k = 0;
            for (int j = maximumBit - 1; j >= 0; --j) {
                if ((xs >> j & 1) == 0) {
                    k |= 1 << j;
                }
            }
            ans[i] = k;
            xs ^= x;
        }
        return ans;
    }
}
```

### Java

```java
class Solution {
public
  int[] getMaximumXor(int[] nums, int maximumBit) {
    int n = nums.length;
    int xs = 0;
    for (int x : nums) {
      xs ^= x;
    }
    int[] ans = new int[n];
    for (int i = 0; i < n; ++i) {
      int x = nums[n - i - 1];
      int k = 0;
      for (int j = maximumBit - 1; j >= 0; --j) {
        if (((xs >> j) & 1) == 0) {
          k |= 1 << j;
        }
      }
      ans[i] = k;
      xs ^= x;
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} maximumBit * @return {number[]} */ var getMaximumXor =
  function (nums, maximumBit) {
    let xs = 0;
    for (const x of nums) {
      xs ^= x;
    }
    const n = nums.length;
    const ans = new Array(n);
    for (let i = 0; i < n; ++i) {
      const x = nums[n - i - 1];
      let k = 0;
      for (let j = maximumBit - 1; j >= 0; --j) {
        if (((xs >> j) & 1) == 0) {
          k |= 1 << j;
        }
      }
      ans[i] = k;
      xs ^= x;
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  vector<int> getMaximumXor(vector<int> &nums, int maximumBit) {
    int xs = 0;
    for (int &x : nums) {
      xs ^= x;
    }
    int n = nums.size();
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
      int x = nums[n - i - 1];
      int k = 0;
      for (int j = maximumBit - 1; ~j; --j) {
        if ((xs >> j & 1) == 0) {
          k |= 1 << j;
        }
      }
      ans[i] = k;
      xs ^= x;
    }
    return ans;
  }
};

```

### Python

```python
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

```