1829. Maximum XOR for Each Query LeetCode Solution

In this guide, you will get 1829. Maximum XOR for Each Query LeetCode Solution with the best time and space complexity. The solution to Maximum XOR for Each Query problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum XOR for Each Query solution in C++
Maximum XOR for Each Query solution in Java
Maximum XOR for Each Query solution in Python
Additional Resources

1829. Maximum XOR for Each Query LeetCode Solution image

Problem Statement of 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:

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.
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.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

1829. Maximum XOR for Each Query LeetCode Solution in C++

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

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

    ranges::reverse(ans);
    return ans;
  }
};
/* code provided by PROGIEZ */

1829. Maximum XOR for Each Query LeetCode Solution in Java

class Solution {
  public int[] getMaximumXor(int[] nums, int maximumBit) {
    final int n = nums.length;
    final int mx = (1 << maximumBit) - 1;
    int[] ans = new int[n];
    int xors = 0;

    for (int i = 0; i < n; ++i) {
      xors ^= nums[i];
      ans[n - 1 - i] = xors ^ mx;
    }

    return ans;
  }
}
// code provided by PROGIEZ

1829. Maximum XOR for Each Query LeetCode Solution in Python

class Solution:
  def getMaximumXor(self, nums: list[int], maximumBit: int) -> list[int]:
    mx = (1 << maximumBit) - 1
    ans = []
    xors = 0

    for num in nums:
      xors ^= num
      ans.append(xors ^ mx)

    return ans[::-1]
 # code by PROGIEZ