LeetCode 1829 - Maximum XOR for Each Query

The problem gives us a sorted array nums and an integer maximumBit. For every query, we must choose a number k such that: - 0 <= k < 2^maximumBit - The value of: is as large as possible.

leetcodemediumarraybit-manipulationprefix-sum

LeetCode Problem 1829

Difficulty: 🟡 Medium
Topics: Array, Bit Manipulation, Prefix Sum

Solution

Problem Understanding

The problem gives us a sorted array nums and an integer maximumBit. For every query, we must choose a number k such that:

  • 0 <= k < 2^maximumBit
  • The value of:
nums[0] XOR nums[1] XOR ... XOR nums[last] XOR k

is as large as possible.

After answering the query, we remove the last element from the array and repeat the process until the array becomes empty.

The important detail is that the answer for each query depends on the XOR of all currently remaining elements. Since the array shrinks from the end after every query, we repeatedly compute answers for progressively smaller prefixes of the array.

The output is an array where:

  • answer[0] corresponds to the full array
  • answer[1] corresponds to the array after removing the last element once
  • and so on

The constraints are important:

  • n can be as large as 10^5
  • maximumBit can be up to 20

A quadratic solution would be far too slow because repeatedly recomputing XORs for every query would require too many operations.

Another important observation is that every number in nums is guaranteed to be smaller than 2^maximumBit. This means every relevant value fits within exactly maximumBit bits.

Although the problem states that the array is sorted, the sorting property is actually irrelevant for solving the problem. XOR operations do not depend on order.

Several edge cases are worth noting early:

  • A single-element array
  • Arrays where all elements are zero
  • Maximum possible bit sizes
  • Situations where the XOR already equals the maximum possible value
  • Repeated values, since XOR cancels identical pairs

Understanding how XOR behaves is the key to solving this problem efficiently.

Approaches

Brute Force Approach

A straightforward solution would process each query independently.

For every query:

  1. Compute the XOR of all current elements.
  2. Try every possible value of k from 0 to 2^maximumBit - 1.
  3. Compute:
currentXor XOR k
  1. Choose the k that produces the maximum value.
  2. Remove the last element and continue.

This approach is correct because it explicitly checks every valid candidate for k.

However, it is extremely inefficient.

If there are n queries and each query tries up to 2^maximumBit possible values, the complexity becomes enormous. Since maximumBit can be 20, we may need to test over one million candidates per query.

This is completely impractical for n = 10^5.

Key Insight

To maximize:

currentXor XOR k

we want every bit in the result to become 1.

The largest number representable with maximumBit bits is:

(1 << maximumBit) - 1

For example:

  • maximumBit = 2 → maximum value is 3 → binary 11
  • maximumBit = 3 → maximum value is 7 → binary 111

Suppose:

mask = (1 << maximumBit) - 1

Then the best possible k is:

k = currentXor XOR mask

Why?

Because XOR flips bits:

  • If a bit in currentXor is 0, we want k to contribute 1
  • If a bit in currentXor is 1, we want k to contribute 0

This guarantees:

currentXor XOR k = mask

which is the maximum possible value.

We also avoid recomputing XOR from scratch each time.

If:

currentXor = XOR of all current elements

then after removing the last element x:

newXor = currentXor XOR x

because XOR is reversible.

This gives us a linear-time solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n * 2^maximumBit) O(1) Tries every possible value of k for each query
Optimal O(n) O(1) excluding output Uses XOR properties and a bitmask

Algorithm Walkthrough

  1. Compute the XOR of all elements in nums.

This represents the XOR value for the first query, since the first query uses the full array. 2. Create a mask containing all maximumBit bits set to 1.

The formula is:

mask = (1 << maximumBit) - 1

For example:

  • maximumBit = 2 → 11 in binary
  • maximumBit = 3 → 111 in binary
  1. Initialize an empty result array.

We will append answers in query order. 4. For each query:

  • Compute:
k = currentXor XOR mask
  • Append k to the result.

This works because XOR with the mask flips exactly the bits needed to produce the largest possible value. 5. Remove the last element logically.

Instead of modifying the array, update the running XOR:

currentXor ^= nums[lastIndex]

XORing again with the same number removes its contribution. 6. Continue until all elements are processed. 7. Return the result array.

Why it works

The algorithm relies on the fact that the maximum value representable using maximumBit bits is a number where all those bits are 1.

For every query, we choose k so that:

currentXor XOR k = mask

Since XOR can independently control each bit, choosing:

k = currentXor XOR mask

guarantees the result equals the maximum possible value.

The running XOR update is also correct because XOR is self-inverse:

a XOR b XOR b = a

Therefore, removing an element from the cumulative XOR requires only another XOR operation.

Python Solution

from typing import List

class Solution:
    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
        current_xor = 0

        for num in nums:
            current_xor ^= num

        mask = (1 << maximumBit) - 1

        answer = []

        for i in range(len(nums) - 1, -1, -1):
            best_k = current_xor ^ mask
            answer.append(best_k)

            current_xor ^= nums[i]

        return answer

The implementation begins by computing the XOR of the entire array. This value represents the XOR for the first query.

Next, the code creates the bitmask:

mask = (1 << maximumBit) - 1

This mask represents the largest value possible within the allowed bit range.

The loop iterates backward through the array because each query removes the last remaining element.

For every iteration:

best_k = current_xor ^ mask

computes the optimal value of k.

After storing the answer, the code removes the contribution of the current last element:

current_xor ^= nums[i]

This efficiently prepares the XOR for the next query without recomputing from scratch.

Finally, the completed answer array is returned.

Go Solution

func getMaximumXor(nums []int, maximumBit int) []int {
	currentXor := 0

	for _, num := range nums {
		currentXor ^= num
	}

	mask := (1 << maximumBit) - 1

	answer := make([]int, 0, len(nums))

	for i := len(nums) - 1; i >= 0; i-- {
		bestK := currentXor ^ mask
		answer = append(answer, bestK)

		currentXor ^= nums[i]
	}

	return answer
}

The Go implementation follows the exact same logic as the Python version.

A slice is created with preallocated capacity equal to len(nums) for efficiency:

answer := make([]int, 0, len(nums))

Go integers safely handle the constraint range because maximumBit <= 20, so all values remain small.

No special handling is required for empty arrays because the constraints guarantee at least one element.

Worked Examples

Example 1

nums = [0,1,1,3]
maximumBit = 2

First compute total XOR:

0 XOR 1 XOR 1 XOR 3 = 3

Mask:

(1 << 2) - 1 = 3
Query Current Array currentXor mask k = currentXor XOR mask Result
1 [0,1,1,3] 3 3 0 0
2 [0,1,1] 0 3 3 3
3 [0,1] 1 3 2 2
4 [0] 0 3 3 3

Final answer:

[0,3,2,3]

Example 2

nums = [2,3,4,7]
maximumBit = 3

Initial XOR:

2 XOR 3 XOR 4 XOR 7 = 2

Mask:

(1 << 3) - 1 = 7
Query Current Array currentXor mask k Result
1 [2,3,4,7] 2 7 5 5
2 [2,3,4] 5 7 2 2
3 [2,3] 1 7 6 6
4 [2] 2 7 5 5

Final answer:

[5,2,6,5]

Example 3

nums = [0,1,2,2,5,7]
maximumBit = 3

Initial XOR:

0 XOR 1 XOR 2 XOR 2 XOR 5 XOR 7 = 3

Mask:

7
Query Current XOR k
1 3 4
2 4 3
3 1 6
4 3 4
5 1 6
6 0 7

Final answer:

[4,3,6,4,6,7]

Complexity Analysis

Measure Complexity Explanation
Time O(n) One pass to compute XOR and one pass to build answers
Space O(1) excluding output Only a few variables are used besides the result array

The algorithm performs a constant amount of work per element. Every element participates in exactly two XOR operations:

  • once during initial XOR computation
  • once when removed from the running XOR

No auxiliary data structures proportional to input size are required.

Test Cases

from typing import List

class Solution:
    def getMaximumXor(self, nums: List[int], maximumBit: int) -> List[int]:
        current_xor = 0

        for num in nums:
            current_xor ^= num

        mask = (1 << maximumBit) - 1

        answer = []

        for i in range(len(nums) - 1, -1, -1):
            answer.append(current_xor ^ mask)
            current_xor ^= nums[i]

        return answer

solution = Solution()

# Provided example 1
assert solution.getMaximumXor([0, 1, 1, 3], 2) == [0, 3, 2, 3]

# Provided example 2
assert solution.getMaximumXor([2, 3, 4, 7], 3) == [5, 2, 6, 5]

# Provided example 3
assert solution.getMaximumXor([0, 1, 2, 2, 5, 7], 3) == [4, 3, 6, 4, 6, 7]

# Single element array
assert solution.getMaximumXor([0], 1) == [1]

# Single non-zero element
assert solution.getMaximumXor([5], 3) == [2]

# All zeros
assert solution.getMaximumXor([0, 0, 0], 2) == [3, 3, 3]

# Repeated numbers cancel out
assert solution.getMaximumXor([1, 1, 1, 1], 2) == [3, 2, 3, 2]

# Maximum bit boundary
assert solution.getMaximumXor([1048575], 20) == [0]

# Increasing values
assert solution.getMaximumXor([1, 2, 3, 4], 3) == [3, 7, 4, 6]

# Large XOR transitions
assert solution.getMaximumXor([7, 7, 7], 3) == [0, 7, 0]
Test Why
[0,1,1,3], 2 Validates provided example
[2,3,4,7], 3 Validates changing XOR states
[0,1,2,2,5,7], 3 Tests repeated values and removals
[0], 1 Smallest possible array
[5], 3 Single non-zero value
[0,0,0], 2 XOR remains zero throughout
[1,1,1,1], 2 Tests XOR cancellation behavior
[1048575], 20 Maximum allowed bit range
[1,2,3,4], 3 General mixed values
[7,7,7], 3 Alternating XOR patterns

Edge Cases

A single-element array is an important edge case because there is only one query. A buggy implementation might incorrectly attempt to remove elements before computing the answer or mishandle indexing when iterating backward. The solution handles this naturally because the loop computes the answer first and only then removes the element from the running XOR.

Arrays containing many zeros are another important case. Since XOR with zero changes nothing, the cumulative XOR may remain constant across multiple queries. Some implementations incorrectly assume the XOR value always changes after removing an element. This implementation correctly updates using XOR properties, so zero values are handled automatically.

Repeated values can also create subtle bugs because XOR cancels identical pairs:

x XOR x = 0

For example, an array like [1,1,1,1] produces alternating XOR states as elements are removed. The algorithm correctly maintains the running XOR incrementally, so cancellation effects are handled without any special logic.

The maximum bit boundary is another important consideration. When maximumBit = 20, the mask becomes:

(1 << 20) - 1

The implementation safely computes this value in both Python and Go without overflow issues because all values remain well within standard integer limits.