Maximum XOR for Each Query

Med

#1672Time: O(n^2) - The outer loop runs `n` times for the `n` queries. The inner loop, which calculates the XOR sum, runs `n`, `n-1`, `n-2`, ..., `1` times. The total number of XOR operations is the sum of this arithmetic series, which is `n * (n+1) / 2`, resulting in a quadratic time complexity.Space: O(n) - We use an `ArrayList` to store a copy of the numbers, which takes O(n) space. The `answer` array also requires O(n) space.

Patterns

Bit Manipulation Prefix Sum

Data structures

Array

Prompt

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 < 2^maximumBit such that nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k is maximized. k is the answer to the i^th query.
Remove the last element from the current array nums.

Return an array answer, where answer[i] is the answer to the i^th 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 <= 10⁵
1 <= maximumBit <= 20
0 <= nums[i] < 2^maximumBit
nums is sorted in ascending order.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. For each of the n queries, we first calculate the XOR sum of all elements currently in the array. Then, we determine the value of k that would maximize the total XOR sum. This k is stored, and finally, the last element of the array is removed to set up for the next query. This entire process is repeated n times.

Algorithm

1. Initialize an answer array of size n.
1. Create a mutable List from the input nums array to facilitate element removal.
1. Calculate max_val = (1 << maximumBit) - 1. This represents the number with all maximumBit bits set to 1, which is the target for our maximization.
1. Loop n times, from i = 0 to n-1, to simulate each query:
- a. Initialize a variable current_xor = 0.
- b. Iterate through all elements of the current list and compute their bitwise XOR sum, storing it in current_xor.
- c. The value of k that maximizes the expression is k = current_xor ^ max_val.
- d. Store this k in the results: answer[i] = k.
- e. Remove the last element from the list to prepare for the next query.
1. Return the answer array.

Walkthrough

The core idea is to find a non-negative integer k < 2^maximumBit that maximizes the expression (nums[0] XOR ... XOR nums[m-1]) XOR k. The maximum possible value for an expression constrained to maximumBit bits is 2^maximumBit - 1. Let's call this max_val. To achieve this maximum result, we need to have (XOR of current nums) XOR k = max_val. By applying XOR properties, we can solve for k: k = max_val XOR (XOR of current nums).

The brute-force algorithm implements this logic straightforwardly. It iterates n times, and in each iteration, it re-calculates the XOR sum of the shrinking array, computes k, and then removes the last element. Using a dynamic data structure like an ArrayList in Java makes the removal of the last element convenient.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int[] getMaximumXor(int[] nums, int maximumBit) {6        int n = nums.length;7        int[] answer = new int[n];8        List<Integer> currentNums = new ArrayList<>();9        for (int num : nums) {10            currentNums.add(num);11        }12 13        int maxVal = (1 << maximumBit) - 1;14 15        for (int i = 0; i < n; i++) {16            // 1. Calculate current XOR sum17            int currentXor = 0;18            for (int num : currentNums) {19                currentXor ^= num;20            }21 22            // 2. Find k23            int k = currentXor ^ maxVal;24            answer[i] = k;25 26            // 3. Remove the last element27            if (!currentNums.isEmpty()) {28                currentNums.remove(currentNums.size() - 1);29            }30        }31 32        return answer;33    }34}

Complexity

Time

O(n^2) - The outer loop runs `n` times for the `n` queries. The inner loop, which calculates the XOR sum, runs `n`, `n-1`, `n-2`, ..., `1` times. The total number of XOR operations is the sum of this arithmetic series, which is `n * (n+1) / 2`, resulting in a quadratic time complexity.

Space

O(n) - We use an `ArrayList` to store a copy of the numbers, which takes O(n) space. The `answer` array also requires O(n) space.

Trade-offs

Pros

It is simple to understand and implement as it directly translates the problem description into code.
It's a good starting point for understanding the problem mechanics before moving to more optimized solutions.

Cons

The time complexity of O(n^2) is too slow for the given constraints (n <= 10^5), and this solution will likely result in a 'Time Limit Exceeded' error.
It performs a lot of redundant work by re-calculating the XOR sum from scratch in each of the n queries.

This approach significantly improves upon the brute-force method by avoiding the redundant calculation of the XOR sum in each query. We can maintain a running_xor sum. After each query, instead of re-calculating the sum for the smaller array, we can update the running_xor in constant time by XORing it with the element that was just removed. This reduces the overall time complexity from quadratic to linear.

Algorithm

1. Initialize an answer array of size n.
1. Calculate max_val = (1 << maximumBit) - 1.
1. Initialize a variable running_xor = 0.
1. Iterate through the nums array once to calculate the total XOR sum of all its elements and store it in running_xor.
1. Loop n times, from i = 0 to n-1, to answer each query:
- a. The XOR sum for the current query is running_xor. Calculate the required k as k = running_xor ^ max_val.
- b. Store the result: answer[i] = k.
- c. To prepare for the next query, update running_xor by removing the effect of the last element. The last element of the array for query i is nums[n - 1 - i]. Update the sum: running_xor ^= nums[n - 1 - i].
1. Return the answer array.

Walkthrough

The key optimization lies in understanding the properties of the XOR operation. If we have the XOR sum of an array, say X, and we remove the last element y, the new XOR sum is simply X XOR y. This is because (a XOR y) XOR y = a.

Based on this, the algorithm is as follows:

First, we perform a single pass over the entire nums array to compute the initial running_xor. This sum corresponds to the state for the first query.
We calculate max_val = (1 << maximumBit) - 1, which is our target for the maximization.
We then loop n times. In each iteration i, we are answering the i-th query.
- The answer k is found using the current running_xor: k = running_xor ^ max_val.
- We store this k in our result array.
- Then, we update running_xor for the next query (which will have one less element). We do this by XORing running_xor with the element that is conceptually removed, which is nums[n - 1 - i]. This process allows us to find each k in O(1) time after an initial O(n) setup, leading to an efficient O(n) overall solution.

1class Solution {2    public int[] getMaximumXor(int[] nums, int maximumBit) {3        int n = nums.length;4        int[] answer = new int[n];5        6        int maxVal = (1 << maximumBit) - 1;7        8        // Calculate the initial XOR sum of the entire array9        int runningXor = 0;10        for (int num : nums) {11            runningXor ^= num;12        }13        14        // Process the queries from first to last15        for (int i = 0; i < n; i++) {16            // For the current state, find k. The current XOR sum is runningXor.17            answer[i] = runningXor ^ maxVal;18            19            // Update runningXor for the next query by removing the last element.20            // The last element of the current array is nums[n - 1 - i].21            runningXor ^= nums[n - 1 - i];22        }23        24        return answer;25    }26}

Complexity

Time

O(n) - There is an initial loop to calculate the total XOR sum, which takes O(n). The main loop for the queries also runs `n` times, with each step inside being an O(1) operation. Therefore, the total time complexity is O(n) + O(n) = O(n).

Space

O(n) - This is primarily for the output `answer` array. The auxiliary space used for variables like `running_xor` and `maxVal` is O(1).

Trade-offs

Pros

Extremely efficient with a linear time complexity of O(n), which easily passes the given constraints.
This is the optimal solution in terms of time complexity as we must at least look at each element once.
Uses constant auxiliary space (if the output array is not counted).

Cons

It requires a bit more insight to realize that the XOR sum can be updated incrementally rather than recomputed.

Solutions

Solution

1public class Solution {2    public int[] GetMaximumXor(int[] nums, int maximumBit) {3        int xs = 0;4        foreach(int x in nums) {5            xs ^= x;6        }7        int n = nums.Length;8        int[] ans = new int[n];9        for (int i = 0; i < n; ++i) {10            int x = nums[n - i - 1];11            int k = 0;12            for (int j = maximumBit - 1; j >= 0; --j) {13                if ((xs >> j & 1) == 0) {14                    k |= 1 << j;15                }16            }17            ans[i] = k;18            xs ^= x;19        }20        return ans;21    }22}

1class Solution {2public3  int[] getMaximumXor(int[] nums, int maximumBit) {4    int n = nums.length;5    int xs = 0;6    for (int x : nums) {7      xs ^= x;8    }9    int[] ans = new int[n];10    for (int i = 0; i < n; ++i) {11      int x = nums[n - i - 1];12      int k = 0;13      for (int j = maximumBit - 1; j >= 0; --j) {14        if (((xs >> j) & 1) == 0) {15          k |= 1 << j;16        }17      }18      ans[i] = k;19      xs ^= x;20    }21    return ans;22  }23}

1/** * @param {number[]} nums * @param {number} maximumBit * @return {number[]} */ var getMaximumXor =2  function (nums, maximumBit) {3    let xs = 0;4    for (const x of nums) {5      xs ^= x;6    }7    const n = nums.length;8    const ans = new Array(n);9    for (let i = 0; i < n; ++i) {10      const x = nums[n - i - 1];11      let k = 0;12      for (let j = maximumBit - 1; j >= 0; --j) {13        if (((xs >> j) & 1) == 0) {14          k |= 1 << j;15        }16      }17      ans[i] = k;18      xs ^= x;19    }20    return ans;21  };

1class Solution {2public:3  vector<int> getMaximumXor(vector<int> &nums, int maximumBit) {4    int xs = 0;5    for (int &x : nums) {6      xs ^= x;7    }8    int n = nums.size();9    vector<int> ans(n);10    for (int i = 0; i < n; ++i) {11      int x = nums[n - i - 1];12      int k = 0;13      for (int j = maximumBit - 1; ~j; --j) {14        if ((xs >> j & 1) == 0) {15          k |= 1 << j;16        }17      }18      ans[i] = k;19      xs ^= x;20    }21    return ans;22  }23};

1class Solution:2    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]: ans = [] xs = reduce(xor, nums) for x in nums[:: - 1]: k = 0 for i in range(maximumBit - 1, - 1, - 1): if (xs >> i & 1) == 0: k |= 1 << i ans . append(k) xs ^= x return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem