1829. Maximum XOR for Each Query

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.

C++

• 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;
      }
  };

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;
      }
  }

PYTHON 

• from typing import List
  
  class Solution:
      def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
          xs = 0
          for x in nums:
              xs ^= x
  
          n = len(nums)
          ans = [0] * n
          for i in range(n):
              x = nums[n - i - 1]
              k = 0
              for j in range(maximumBit - 1, -1, -1):
                  if (xs >> j & 1) == 0:
                      k |= 1 << j
              ans[i] = k
              xs ^= x
  
          return ans