1829. Maximum XOR for Each Query

Problem Description

In the given problem, we have a sorted array called nums which contains n non-negative integers, and we also have an integer named maximumBit. The goal is to perform n queries by following two steps:

You need to find a non-negative integer k that is less than 2^maximumBit. This integer k, when XORed (^) with the cumulative XOR of all elements in nums, should yield the maximum possible value.
After finding k, remove the last element from the array nums.

We should continue performing these queries until the array nums is empty and return an array answer that contains the results of each query, where answer[i] is the result of the i-th query.

Intuition

To understand the solution, we first need to understand the properties of the XOR operation:

XOR of a number with itself is 0.
XOR of a number with 0 is the number itself.
XOR is associative and commutative, which means the order of operands doesn't affect the result.

Given these properties and the fact that we want to maximize the result of XORing the cumulative XOR of the nums array with k, an efficient way to do this is by considering what makes a number bigger in binary terms. A number is bigger if it has more significant bits set to 1. Since the array nums is sorted and we want to maximize the XOR result, we can iteratively calculate the cumulative XOR of the numbers in the reverse order (starting from the end), because, on each query, we are removing the last element.

For each cumulative XOR value, we want to find the best k such that cumulative XOR ^ k is as large as possible. As k should be less than 2^maximumBit, we can generate a mask that has all bits set up to maximumBit (by doing (1 << maximumBit) - 1). By XORing the cumulative XOR with this mask, we're essentially flipping all the bits of the cumulative XOR within the range allowed by maximumBit. This flipping ensures that we get the biggest number possible since, if a bit in the cumulative XOR is 0, it gets flipped to 1, and since we start with the most significant bit down to the least, we maximize the result. The answer for each query is then this maximized XOR value.

So, the solution code does this in the following steps:

It initializes an empty list ans to store the answer for each query.
It calculates the initial cumulative XOR of all elements in nums with reduce(xor, nums).
It creates a mask to define the range of valid values for k with (1 << maximumBit) - 1.
Lastly, it iterates through each number in nums in reverse, finds the answer for each query using the mask, appends it to ans, and updates xs by XORing it with the current element being removed - effectively calculating the new cumulative XOR for the next query.

The computed ans array is returned as the final result.

Learn more about Prefix Sum patterns.

Solution Approach

The implementation of the provided solution leverages the cumulative XOR property and bit manipulation to answer each query efficiently. Let's walk through the crucial steps involved:

Accumulate the Global XOR: The solution first employs the reduce function with the xor operator from Python's functools to compute the cumulative XOR (xs) of all elements in the array nums. This step gives us the starting point for performing our queries.
```
xs = reduce(xor, nums)
```
Prepare the Mask: A mask is prepared using bitwise left shift and subtraction:
```
mask = (1 << maximumBit) - 1
```
This creates a number where all bits less than maximumBit are set to 1. The purpose of the mask is to invert the bits in the cumulative XOR within the range specified by maximumBit.
Iterate in Reverse: The solution then iterates through nums in reverse. The purpose of iterating in reverse is to simulate the step-by-step removal of the last element from the nums array after each query, as required by the problem statement.
```
for x in nums[::-1]:
```
Find k and Update: In each iteration, the current cumulative XOR (xs) is XORed with the mask to find the desired k. This k is the number that, when XORed with the current cumulative XOR, yields the maximum result under the constraints of maximumBit.
```
k = xs ^ mask
```
k is then appended to the answer array ans. After finding the answer to the current query and before moving on to the next iteration (the next query), xs is updated by XORing it with the current number x. This effectively removes the last element of the nums in the cumulative XOR perspective.
```
ans.append(k)
xs ^= x
```
Return the Result: After completing all iterations, the list ans contains the answers to all n queries in the respective order. The list ans is then returned.

The approach notably utilizes bitwise operations, a mask to flip relevant bits to maximize XOR results, and iterates in reverse to simulate the query process without manually updating the array. Data structures used include only the input list nums and the output list ans. The code is efficient as it does not use extra space for a modified array and has a time complexity of O(n) where n is the number of elements in nums, as it requires just one iteration over the array elements.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's assume nums is [3, 8, 2] and maximumBit is 3. The goal is to find a non-negative integer k for each query, which gives us the maximum possible value when XORed with the cumulative XOR of all elements in nums, then remove the last element from nums.

We'll start by calculating the cumulative XOR of the entire array nums:

xs = reduce(xor, nums)  # xs = 3 ^ 8 ^ 2 = 9

Next, we'll prepare the mask:

mask = (1 << maximumBit) - 1  # mask = (1 << 3) - 1 = 7 (binary 111)

Now, let's walk through the steps for each query in our example:

First Query:

Starting with the full array [3, 8, 2], our cumulative XOR, xs is 9 (binary 1001), and the mask is 7 (binary 0111).

k = xs ^ mask  # k = 9 ^ 7 = 14 (binary 1110)

We append 14 to our answers array, ans = [14], and remove the last element from nums.

Update xs:

xs ^= nums[-1]  # xs ^= 2 (xs was 9, now it is 11, binary 1011)
nums.pop()  # Updated nums = [3, 8]

Second Query:

With the updated array [3, 8], our new xs is 11 (binary 1011).

k = xs ^ mask  # k = 11 ^ 7 = 12 (binary 1100)

We append 12 to our answers array, ans = [14, 12], and remove the last element from nums.

Update xs:

xs ^= nums[-1]  # xs ^= 8 (xs was 11, now it is 3, binary 0011)
nums.pop()  # Updated nums = [3]

Third Query:

The updated array now is just [3], xs is 3 (binary 0011).
```
k = xs ^ mask  # k = 3 ^ 7 = 4 (binary 0100)
```
We append 4 to our answers array, ans = [14, 12, 4], and now nums becomes empty.

Since the nums array is now empty, our process stops here. We return the results array ans:

return ans  # [14, 12, 4]

In summary, our small example outputs the results [14, 12, 4] for the respective queries. Each number represents the maximum value achievable for k by XORing with the cumulative XOR of the remaining array nums at each step.

Solution Implementation

1from functools import reduce # Import the reduce function from the functools module
2from operator import xor # Import the xor function from the operator module
3from typing import List # Import List type for type hinting
4
5class Solution:
6    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
7        # Intialize an empty list to store the answers
8        answers = []
9      
10        # Perform XOR on all elements in nums to get the initial xor_sum
11        xor_sum = reduce(xor, nums)
12      
13        # Create a mask which will have ones for the number of maximumBit bits
14        mask = (1 << maximumBit) - 1
15      
16        # Iterate over the nums list in reverse order
17        for num in reversed(nums):
18            # Calculate k as XOR of xor_sum with mask to get the maximum XOR value
19            k = xor_sum ^ mask
20            # Append the resultant k to the answers list
21            answers.append(k)
22            # Update the xor_sum by XORing it with the current number
23            xor_sum ^= num
24          
25        # Return the list of answers
26        return answers
27

1class Solution {
2    public int[] getMaximumXor(int[] nums, int maximumBit) {
3        // Initialize 'xorSum' to store the cumulative XOR of all elements in 'nums'.
4        int xorSum = 0;
5      
6        // Calculate the cumulative XOR for all the elements in 'nums'.
7        for (int num : nums) {
8            xorSum ^= num;
9        }
10      
11        // Calculate the mask by considering the maximum number of bits.
12        // The mask will be a number with 'maximumBit' number of 1s in binary representation.
13        int mask = (1 << maximumBit) - 1;
14      
15        // The length of the input array.
16        int length = nums.length;
17      
18        // Initialize an array 'maximumXors' to hold the maximum XOR for each element in reverse order.
19        int[] maximumXors = new int[length];
20      
21        // Iterate over the 'nums' array in reverse, computing the maximum XOR for each prefix.
22        for (int i = 0; i < length; ++i) {
23            // XOR the current cumulative sum with the mask to find the maximum XOR value.
24            int maxXor = xorSum ^ mask;
25          
26            // Add the maximum XOR value to the result array.
27            maximumXors[i] = maxXor;
28          
29            // Update the 'xorSum' to remove the contribution of the current element because
30            // we are moving from the end of the array towards the start.
31            int currentNum = nums[length - i - 1];
32            xorSum ^= currentNum;
33        }
34      
35        // Return the array of maximum XOR values.
36        return maximumXors;
37    }
38}
39

1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6    vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
7        // Initialize a variable to store the cumulative XOR of all numbers
8        int cumulativeXor = 0;
9
10        // Calculate the cumulative XOR for the whole array
11        for (int num : nums) {
12            cumulativeXor ^= num;
13        }
14
15        // Compute the bitmask with all bits set to 1 up to the maximumBit
16        int mask = (1 << maximumBit) - 1;
17      
18        // Get the size of the input array
19        int n = nums.size();
20
21        // Initialize the answer vector with the same size as the input array
22        vector<int> answer(n);
23
24        // Iterate over the array to find the maximum XOR for each element
25        for (int i = 0; i < n; ++i) {
26            // Compute the XOR of the current xor state with the mask to find the maximum XOR
27            int maxXor = cumulativeXor ^ mask;
28            answer[i] = maxXor;
29
30            // Update the cumulative XOR by removing the current element (from the end)
31            cumulativeXor ^= nums[n - i - 1];
32        }
33
34        // Return the vector containing the maximum XOR values
35        return answer;
36    }
37};
38

1function getMaximumXor(nums: number[], maximumBit: number): number[] {
2    // Initialize the cumulative XOR variable.
3    let cumulativeXor = 0;
4  
5    // Compute the cumulative XOR for all numbers in the array.
6    for (const num of nums) {
7        cumulativeXor ^= num;
8    }
9  
10    // Calculate the mask to get the maximum XOR by setting maximumBit bits to 1
11    const mask = (1 << maximumBit) - 1;
12  
13    // Determine the number of elements in the numbers array.
14    const length = nums.length;
15  
16    // Initialize the answer array with the same length as the input array.
17    const answer = new Array(length);
18  
19    // Iterate over the numbers to calculate the maximum XOR for each number
20    // in reverse order.
21    for (let i = 0; i < length; ++i) {
22        // Find the current number by indexing from the end of the nums array.
23        const currentNum = nums[length - i - 1];
24      
25        // Calculate the maximum XOR for the current number as per the problem statement.
26        let maxXor = cumulativeXor ^ mask;
27      
28        // Store the maximum XOR in the answer array.
29        answer[i] = maxXor;
30      
31        // Update the cumulative XOR by removing the effect of the current number.
32        cumulativeXor ^= currentNum;
33    }
34  
35    // Return the answer array containing maximum XORs.
36    return answer;
37}
38

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by several factors:

The reduce(xor, nums) operation, which computes the XOR of all elements in the nums list. This operation takes O(n) time, where n is the length of nums.
The loop that reverses nums and computes the maximum XOR for each prefix. The reversal is O(n) due to the slicing operation nums[::-1], and the loop runs n times. Inside the loop, the XOR computation and the assignment xs ^= x both take constant time O(1).

Therefore, the total time complexity is O(n) due to the linear scan through all elements of nums.

Space Complexity

The space complexity of the code is also influenced by several parts:

The ans list that stores the maximum XOR values for each prefix, which will contain n elements at the end of the execution. This contributes O(n) to the space complexity.
The constants xs and mask use O(1) space.
The reversed nums nums[::-1] creates a new list, which also takes O(n) space.

However, the space used for input (such as nums) is typically not counted in space complexity analysis, as this is considered space that the algorithm needs to read its input rather than working space used by the algorithm. With that convention, the auxiliary space complexity of this algorithm is O(n), owing to the ans list. If you do include the space taken by nums[::-1], the space complexity would still be O(n).

In conclusion, the time complexity of the code is O(n), and the space complexity of the code is O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a good use case for backtracking?

Combinatorial problems

Random number generation

Topological sorting

Matrix multiplication

I don't know