Maximum XOR for Each Query

MEDIUM

Description

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:
1^st query: nums = [0,1,1,3], k = 0 since 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3.
2^nd query: nums = [0,1,1], k = 3 since 0 XOR 1 XOR 1 XOR 3 = 3.
3^rd query: nums = [0,1], k = 2 since 0 XOR 1 XOR 2 = 3.
4^th 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:
1^st query: nums = [2,3,4,7], k = 5 since 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7.
2^nd query: nums = [2,3,4], k = 2 since 2 XOR 3 XOR 4 XOR 2 = 7.
3^rd query: nums = [2,3], k = 6 since 2 XOR 3 XOR 6 = 7.
4^th 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

Checkout 2 different approaches to solve Maximum XOR for Each Query. Click on different approaches to view the approach and algorithm in detail.

Brute Force Simulation

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.

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.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int[] getMaximumXor(int[] nums, int maximumBit) {
        int n = nums.length;
        int[] answer = new int[n];
        List<Integer> currentNums = new ArrayList<>();
        for (int num : nums) {
            currentNums.add(num);
        }

        int maxVal = (1 << maximumBit) - 1;

        for (int i = 0; i < n; i++) {
            // 1. Calculate current XOR sum
            int currentXor = 0;
            for (int num : currentNums) {
                currentXor ^= num;
            }

            // 2. Find k
            int k = currentXor ^ maxVal;
            answer[i] = k;

            // 3. Remove the last element
            if (!currentNums.isEmpty()) {
                currentNums.remove(currentNums.size() - 1);
            }
        }

        return answer;
    }
}

Complexity Analysis

Time Complexity: 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 Complexity: 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.

Pros and Cons

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.

Code Solutions

Checking out 5 solutions in different languages for Maximum XOR for Each Query. Click on different languages to view the code.

public class Solution {
    public int[] GetMaximumXor(int[] nums, int maximumBit) {
        int xs = 0;
        foreach(int x in nums) {
            xs ^= x;
        }
        int n = nums.Length;
        int[] ans = new int[n];
        for (int i = 0; i < n; ++i) {
            int x = nums[n - i - 1];
            int k = 0;
            for (int j = maximumBit - 1; j >= 0; --j) {
                if ((xs >> j & 1) == 0) {
                    k |= 1 << j;
                }
            }
            ans[i] = k;
            xs ^= x;
        }
        return ans;
    }
}

Video Solution

Watch the video walkthrough for Maximum XOR for Each Query

Patterns:

Bit ManipulationPrefix Sum

Data Structures:

Array