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
- Calculate the maximum possible integer
max
that can be achieved givenmaximumBit
. This can be calculated as(1 << maximumBit) - 1
. - Initialize an empty list
ans
for storing the result of each query. - Calculate the XOR of all the elements in the input array
nums
. This can be done using a single variablexors
initialized with 0, and updating it with each XOR operation. - For each element
num
innums
, calculate the XOR ofxors
andmax
, and append the result to theans
list. - 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
.
-
Calculate the maximum possible integer
max
that can be achieved withmaximumBit
. In this case,max = (1 << 3) - 1 = 7
. -
Initialize an empty list
ans
for storing the result of each query. -
Calculate the XOR of all the elements in the input array
nums
.1xors = 0 XOR 1 XOR 2 XOR 2 XOR 5 XOR 7
-
For each element
num
innums
, calculate the XOR ofxors
andmax
: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]
-
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;
13 ans.add(xors ^ max);
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;
12 ans.Add(xors ^ max);
13 }
14
15 ans.Reverse();
16 return ans.ToArray();
17 }
18}
19
20```In conclusion, the problem of finding 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 can be solved with a simple, iterative algorithm. The algorithm involves calculating the XOR of all the elements in the input array for each query, then appending the result of this XOR operation with the maximum possible integer given `maximumBit`. Once all the queries have been executed and their results stored in an `ans` list/array, reverse this list/array and return it as the final output. We demonstrated implementations of this algorithm in Python, Java, JavaScript, C++, and C#.