LetCode 1829. Maximum XOR value per query

1829. The maximum XOR value of each query

To give you one Orderly Array nums , It consists of n It's a nonnegative integer , I'll give you an integer at the same time maximumBit . You need to perform the following query n Time ：

1. Find a nonnegative integer k < 2maximumBit , bring nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k Result Maximize .k It's No i The answer to a query .
2. From the current array nums Delete Last An element .

Please return an array answer , among answer[i] It's No i The result of a query .

Example 1：

 Input ：nums = [0,1,1,3], maximumBit = 2
 Output ：[0,3,2,3]
 explain ： The answers to the query are as follows ：
 First query ：nums = [0,1,1,3],k = 0, because  0 XOR 1 XOR 1 XOR 3 XOR 0 = 3 .
 The second query ：nums = [0,1,1],k = 3, because  0 XOR 1 XOR 1 XOR 3 = 3 .
 The third query ：nums = [0,1],k = 2, because  0 XOR 1 XOR 2 = 3 .
 The fourth query ：nums = [0],k = 3, because  0 XOR 3 = 3 .

Example 2：

 Input ：nums = [2,3,4,7], maximumBit = 3
 Output ：[5,2,6,5]
 explain ： The answers to the query are as follows ：
 First query ：nums = [2,3,4,7],k = 5, because  2 XOR 3 XOR 4 XOR 7 XOR 5 = 7.
 The second query ：nums = [2,3,4],k = 2, because  2 XOR 3 XOR 4 XOR 2 = 7 .
 The third query ：nums = [2,3],k = 6, because  2 XOR 3 XOR 6 = 7 .
 The fourth query ：nums = [2],k = 5, because  2 XOR 5 = 7 .

Example 3：

 Input ：nums = [0,1,2,2,5,7], maximumBit = 3
 Output ：[4,3,6,4,6,7]

Tips ：

• nums.length == n
• 1 <= n <= 105
• 1 <= maximumBit <= 20
• 0 <= nums[i] < 2maximumBit
• nums The number in has been pressed Ascending Arrange order well .

Two 、 Method 1

An operation

class Solution {
    
    public int[] getMaximumXor(int[] nums, int maximumBit) {
    
        int t = (1 << maximumBit)-1;
        int n = nums.length;
        int[] ans = new int[n];
        ans[n-1] = nums[0] ^ t;
        for(int i = 1; i < n; i++){
    
            nums[i] ^= nums[i-1];
            ans[n-1-i] = nums[i] ^ t;
        }
        return ans;
    }
}

Complexity analysis

• Time complexity ：O(n).

• Spatial complexity ：O(1). The space required to store the returned answer is not included here .