Maximum XOR for Each Query

Leetcode Problem:

• Maximum XOR for Each Query

Summary

• Given a sorted array of non-negative integers and an integer maximumBit, find the maximum XOR value for each query and return the answers.

Approach

• The solution uses the XOR operation to find the maximum XOR value for each query
• It initializes the accumulator with the XOR of all numbers in the array, then iterates through the array from right to left, updating the accumulator with the XOR of the current number and the maximum possible XOR value
• The result is the XOR of the accumulator and the maximum possible XOR value, which is the maximum XOR value for the current query.

Complexity

• O(n) where n is the number of elements in the array, as it only requires a single pass through the array.

Explanation

• The solution starts by initializing the accumulator with the XOR of all numbers in the array
• This is done to ensure that the maximum XOR value for the first query is correctly calculated
• Then, it iterates through the array from right to left, updating the accumulator with the XOR of the current number and the maximum possible XOR value
• The result is the XOR of the accumulator and the maximum possible XOR value, which is the maximum XOR value for the current query
• This process is repeated for each query, and the results are stored in the result vector.

Solution Code:

class Solution {
public:
    vector getMaximumXor(vector& nums, int maximumBit) {
        int max_num = (1 << maximumBit) - 1;
        vector res;
        int acc = 0;
        for(int i = 0 ; i < nums.size(); i++) {
            acc ^= nums[i];
        }

        for(int i = nums.size()-1; i>= 0; i--) {
            res.push_back(acc ^ max_num);
            acc ^= nums[i];
        }
        return res;
    }
};