 # Leetcode 1829. Maximum XOR for Each Query Solution

## Explanation

In this problem, we are given a sorted array of non-negative integers and an integer maximumBit. Our goal is to find an integer `k` (with `0 ≤ k < 2^maximumBit`) such that the final resultant value of the XOR of all the array elements and `k` is maximized. We need to perform this query `n` times, removing the last element from the array each time and finding a new `k`. We can achieve this by applying an iterative algorithm that calculates the XOR of all the elements and the corresponding `k`.

### Approach

1. Calculate the maximum possible integer `max` that can be achieved given `maximumBit`. This can be calculated as `(1 << maximumBit) - 1`.
2. Initialize an empty list `ans` for storing the result of each query.
3. Calculate the XOR of all the elements in the input array `nums`. This can be done using a single variable `xors` initialized with 0, and updating it with each XOR operation.
4. For each element `num` in `nums`, calculate the XOR of `xors` and `max`, and append the result to the `ans` list.
5. After all the elements are processed, reverse the `ans` list and return it as the result.

Let's walk through an example to understand the working of the algorithm better:

### Example

Consider the input `nums = [0, 1, 2, 2, 5, 7]` and `maximumBit = 3`.

1. Calculate the maximum possible integer `max` that can be achieved with `maximumBit`. In this case, `max = (1 << 3) - 1 = 7`.

2. Initialize an empty list `ans` for storing the result of each query.

3. Calculate the XOR of all the elements in the input array `nums`.

``1xors = 0 XOR 1 XOR 2 XOR 2 XOR 5 XOR 7``
4. For each element `num` in `nums`, calculate the XOR of `xors` and `max`:

``````10: 7 XOR 0 = 7
21: 6 XOR 1 = 7
32: 5 XOR 2 = 7
42: 4 XOR 2 = 6
55: 3 XOR 5 = 6
67: 0 XOR 7 = 7``````

Append the results to the `ans` list:

``1ans = [7, 7, 7, 6, 6, 7]``
5. Reverse the `ans` list and return it as the result:

``1ans = [4, 3, 6, 4, 6, 7]``

Now, let's implement this algorithm in different programming languages.

## Python Solution

``````1class Solution:
2    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
3        max_value = (1 << maximumBit) - 1
4        ans = []
5        xors = 0
6
7        for num in nums:
8            xors ^= num
9            ans.append(xors ^ max_value)
10
11        ans.reverse()
12        return ans``````

## Java Solution

``````1import java.util.ArrayList;
2import java.util.Collections;
3import java.util.List;
4
5class Solution {
6    public List<Integer> getMaximumXor(int[] nums, int maximumBit) {
7        int max = (1 << maximumBit) - 1;
8        List<Integer> ans = new ArrayList<>();
9        int xors = 0;
10
11        for (int num : nums) {
12            xors ^= num;
14        }
15
16        Collections.reverse(ans);
17        return ans;
18    }
19}``````

## JavaScript Solution

``````1class Solution {
2  getMaximumXor(nums, maximumBit) {
3    const max = (1 << maximumBit) - 1;
4    let ans = [];
5    let xors = 0;
6
7    for (const num of nums) {
8      xors ^= num;
9      ans.push(xors ^ max);
10    }
11
12    ans.reverse();
13    return ans;
14  }
15}``````

## C++ Solution

``````1#include <algorithm>
2#include <vector>
3
4class Solution {
5 public:
6  std::vector<int> getMaximumXor(std::vector<int>& nums, int maximumBit) {
7    const int max = (1 << maximumBit) - 1;
8    std::vector<int> ans;
9    int xors = 0;
10
11    for (const int num : nums) {
12      xors ^= num;
13      ans.push_back(xors ^ max);
14    }
15
16    std::reverse(ans.begin(), ans.end());
17    return ans;
18  }
19};``````

## C# Solution

``````1using System;
2using System.Collections.Generic;
3
4public class Solution {
5    public int[] GetMaximumXor(int[] nums, int maximumBit) {
6        int max = (1 << maximumBit) - 1;
7        List<int> ans = new List<int>();
8        int xors = 0;
9
10        foreach (int num in nums) {
11            xors ^= num;