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

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.

Approach 01:

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
        const int maxXorValue = (1 << maximumBit) - 1;  // Maximum value with all bits set to 1
        vector<int> result;
        int cumulativeXor = 0;

        for (const int num : nums) {
            cumulativeXor ^= num;
            result.push_back(cumulativeXor ^ maxXorValue);
        }

        // Reverse the result vector to match the required order
        reverse(result.begin(), result.end());
        return result;
    }
};

from typing import List

class Solution:
    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
        maxXorValue = (1 << maximumBit) - 1  # Maximum value with all bits set to 1
        result = []
        cumulativeXor = 0

        for num in nums:
            cumulativeXor ^= num
            result.append(cumulativeXor ^ maxXorValue)

        # Reverse the result list to match the required order
        result.reverse()
        return result

Time Complexity

• Loop over the Input Array:

  The function iterates over each element in the input array nums exactly once. This loop has a time complexity of \( O(N) \), where \( N \) is the size of the nums array.

• Reverse Operation:

  The function uses reverse(result.begin(), result.end()), which also takes \( O(N) \) time. However, since it’s independent of the previous loop, it does not affect the overall time complexity significantly.

• Overall Time Complexity:

  The overall time complexity is \( O(N) + O(N) = O(N) \).

Space Complexity

• Result Vector:

  The function uses an additional vector result to store the output, which has a size of \( N \). Thus, it requires \( O(N) \) extra space.

• Auxiliary Variables:

  The function uses a few variables like cumulativeXor and maxXorValue, which take up constant space \( O(1) \).

• Overall Space Complexity:

  The overall space complexity is \( O(N) \) due to the result vector.