---
# System prepended metadata

title: 1829. Maximum XOR for Each Query
tags: [C++, LeetCode]

---

# LeetCode 1829. Maximum XOR for Each Query

https://leetcode.com/problems/maximum-xor-for-each-query/description/

## 題目大意

給定長度為 `n` 的有序非負整數陣列 `nums`及整數 `maximumBit`

你執行以下操作 `n` 次：

1. 找到一個非負整數 `k`，其中 `k < 2^maximumBit`，使得 `nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k` 的值最大，`k` 即為第 `i` 次操作的答案
2. 從當前的陣列 `nums` 中移除最後一個元素

回傳一個陣列 `answer`，其中 `answer[i]` 是第 `i` 次操作的答案

## 思考

如果被題目給迷惑的人可能不會立刻注意到，每次操作後要使值最大，那個值不用多想，就是 `2^maximumBit - 1`
我們只需要透過 XOR 的特性去反算出 `k` 就好

C++ 參考答案：

```cpp!
class Solution
{
public:
    vector<int> getMaximumXor(vector<int> &nums, int maximumBit)
    {
        const int mx = (1 << maximumBit) - 1;
        vector<int> ans;
        ans.reserve(nums.size());
        int xors = 0;

        for (int num : nums)
        {
            xors ^= num;
            ans.push_back(xors ^ mx);
        }

        reverse(ans.begin(), ans.end());

        return ans;
    }
};
```

Go 參考答案：

```go!
func getMaximumXor(nums []int, maximumBit int) []int {
	mx := (1 << maximumBit) - 1
	n := len(nums)
	ans := make([]int, n)
	xors := 0

	for i, num := range nums {
		xors ^= num
		ans[n-i-1] = xors ^ mx
	}

	return ans
}
```
