【Leetcode】1829. Maximum XOR for Each Query

题目地址：

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

给定一个单调增的长$n$数组$A$，再给定一个数$m,1\le m\le 20$，题目保证$0\le A[i]<2^m$。要求做若干次询问，每次询问求 max ⁡ k < 2 m { A [ 0 ] ∧ . . . ∧ A [ i ] ∧ k } \max_{k<2^m}\{A[0]\wedge...\wedge A[i]\wedge k\} maxk<2m​{A[0]∧...∧A[i]∧k}，询问从$i=n-1,n-2,...,0$依次进行。求询问的结果。

最大值即为$2^m-1$，$k$可以直接求。代码如下：

class Solution {
 public:
  vector<int> getMaximumXor(vector<int>& nums, int m) {
    vector<int> res;
    for (int i = 0, sum = 0; i < nums.size(); i++) {
      sum ^= nums[i];
      res.push_back(sum ^ (1 << m) - 1);
    }

    reverse(res.begin(), res.end());
    return res;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

时间复杂度$O(n)$，空间$O(1)$。