• Posts

Problem 1829 Maximum XOR for Each Query

Problem Statement

Link - Problem 1829

Question

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.

Solution

class Solution {
public:
    vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
        int max_result = (1<<maximumBit)-1;
        int prefix_xor = 0;

        vector<int>result(nums.size());

        for(int i=0;i<nums.size();i++){
            prefix_xor=prefix_xor^nums[i];
            result[nums.size()-1-i] = prefix_xor^max_result;
        }

        return result;

    }
};

Complexity Analysis

| Algorithm                     | Time Complexity | Space Complexity |
| ----------------------------- | --------------- | ---------------- |
| Prefix XOR Array Construction | O(n)            | O(n)             |

Explanation

Intial Thoughts

First, think about what the XOR operation does, it’s like a light switch that turns a bit on or off depending on the input. Then, the goal is to maximize the result, so we should aim to flip as many bits as possible to 1. Given the maximumBit constraint, we need to understand its connection to 2^maximumBit. Think about how this limit can be used to find the maximum value. Lastly, consider how to utilize the prefix XOR to track the current sum and compute the final result.

Intuitive Analysis

To intuitively solve the problem, consider the prefix XOR as a cumulative sum of the current array. Maximize the result by finding the maximum possible value that fits within the 2^maximumBit constraint. The idea of maximizing the result can be linked to flipping all the available bits, which leads to the max_result variable in the solution. Notice that the solution uses this variable in conjunction with the prefix XOR to compute the final result for each step. Lastly, observe how the order of computation is reversed, meaning that the solution processes the array from the end to the beginning, which indicates that the most recently computed prefix XOR is used first.

1. Intuition

• The problem asks to maximize the XOR of the prefix of the array and a number k, where k is less than 2^maximumBit.
• To maximize the XOR, we need to find the maximum possible value of k that can be XORed with the prefix.
• Since the array is sorted, we can use the property of XOR that a^a = 0 and a^0 = a.
• We can calculate the prefix XOR and then XOR it with the maximum possible value of k to get the maximum XOR.
• The maximum possible value of k is (1«maximumBit)-1, which is the maximum value that can be represented by maximumBit bits.
• By XORing the prefix XOR with the maximum possible value of k, we can get the maximum XOR for each prefix.

2. Implementation

• We initialize the maximum result as (1«maximumBit)-1, which is the maximum possible value of k.
• We initialize the prefix XOR as 0, which will store the XOR of the prefix of the array.
• We iterate over the array from left to right and calculate the prefix XOR by XORing the current element with the previous prefix XOR.
• We calculate the maximum XOR for each prefix by XORing the prefix XOR with the maximum result.
• We store the maximum XOR for each prefix in the result array in reverse order.
• We return the result array, which contains the maximum XOR for each prefix.
• The time complexity of this solution is O(n), where n is the size of the array.

Complexity Analysis

Time Complexity:

• The function iterates through each element in the input array nums exactly once in a single loop.
• The dominant operation in this loop is the bitwise XOR operation prefix_xor^nums[i] and prefix_xor^max_result, both of which take constant time, resulting in linear time complexity.
• Since the number of iterations is directly proportional to the input size n, the time complexity is O(n) in all cases - worst, average, and best.

Space Complexity:

• The function creates an additional array result to store the prefix XOR results, which has the same size as the input array nums.
• This extra array contributes to the space complexity, which is O(n), where n is the size of the input array.
• The space usage does not change with the input values or the specific use case, resulting in a consistent space complexity of O(n) for all cases.

Footnote

This question is rated as Medium difficulty.

Hints

Note that the maximum possible XOR result is always 2^(maximumBit) - 1

So the answer for a prefix is the XOR of that prefix XORed with 2^(maximumBit)-1

Similar Questions: