LeetCode 3681 - Maximum XOR of Subsequences

The problem gives us an array nums of non-negative integers. We must choose two subsequences: - The first subsequence has XOR value X. - The second subsequence has XOR value Y. The two subsequences: - May be empty.

leetcodehardarraymathgreedybit-manipulation

LeetCode Problem 3681

Difficulty: 🔴 Hard
Topics: Array, Math, Greedy, Bit Manipulation

Solution

LeetCode 3681 - Maximum XOR of Subsequences

Problem Understanding

The problem gives us an array nums of non-negative integers.

We must choose two subsequences:

  • The first subsequence has XOR value X.
  • The second subsequence has XOR value Y.

The two subsequences:

  • May be empty.
  • Must preserve the original order of elements, as all subsequences do.
  • Are allowed to overlap, meaning the same element can appear in both subsequences.

Our goal is to maximize:

$$X \oplus Y$$

where ⊕ denotes bitwise XOR.

A key observation is that we are not asked to return the subsequences themselves. We only need the maximum possible value of X XOR Y.

The constraints are very large:

  • n can be as large as 100000.
  • nums[i] can be as large as 10^9.

These limits immediately rule out any solution that explicitly enumerates subsequences. Since an array of length n has 2^n subsequences, brute force becomes impossible even for relatively small values of n.

Several edge cases are worth noting:

  • Both subsequences may be empty, producing XOR value 0.
  • Elements may appear in both subsequences simultaneously.
  • The array may contain many zeros.
  • The array may contain repeated values.
  • The optimal answer may require combining several numbers rather than selecting a single large element.

Understanding exactly how overlapping subsequences affect the XOR expression is the key to solving the problem efficiently.

Approaches

Brute Force

A direct approach would enumerate every possible pair of subsequences.

For each subsequence pair:

  1. Compute XOR of the first subsequence.
  2. Compute XOR of the second subsequence.
  3. Compute X XOR Y.
  4. Track the maximum value.

Since there are 2^n possible subsequences, there are:

$$(2^n)^2 = 4^n$$

possible pairs.

This approach is correct because it checks every valid choice, but it is completely infeasible. Even for n = 30, the search space is already enormous.

Key Insight

Let:

  • a_i = 1 if element nums[i] belongs to the first subsequence.
  • b_i = 1 if element nums[i] belongs to the second subsequence.

Then:

$$X = \bigoplus_{a_i=1} nums[i]$$

$$Y = \bigoplus_{b_i=1} nums[i]$$

Therefore:

$$X \oplus Y$$

contains nums[i] exactly when its total contribution appears an odd number of times.

For each element there are four possibilities:

In First In Second Contribution to X XOR Y
No No 0
Yes No nums[i]
No Yes nums[i]
Yes Yes 0

Notice that the only thing that matters is whether the memberships differ.

Define:

$$c_i = a_i \oplus b_i$$

Then:

$$X \oplus Y = \bigoplus_{c_i=1} nums[i]$$

For every element:

  • We can make c_i = 0 by choosing neither subsequence or both subsequences.
  • We can make c_i = 1 by choosing exactly one subsequence.

Therefore every subset of the array is achievable.

The problem becomes:

Find the maximum XOR obtainable from any subset of nums.

This is the classical Maximum Subset XOR problem, which is solved using a linear XOR basis.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(4^n · n) O(n) Enumerates all pairs of subsequences
Optimal O(n · B) O(B) XOR linear basis, where B is number of bits (31 here)

Algorithm Walkthrough

Step 1: Convert the problem

Using the observation above, realize that every achievable value of X XOR Y is exactly the XOR of some subset of nums.

Therefore we only need the maximum subset XOR.

Step 2: Build a linear XOR basis

Maintain an array basis.

Each basis vector represents a unique highest set bit.

For every number:

  1. Let x be the current number.
  2. Process basis vectors from highest bit to lowest bit.
  3. If the leading bit of x already exists in the basis, XOR it away.
  4. Continue until either:
  • x becomes 0, meaning it is linearly dependent, or
  • we find a new leading bit and insert x into the basis.

This is analogous to Gaussian elimination over binary arithmetic.

Step 3: Construct the maximum XOR

Once the basis is built:

  1. Start with answer = 0.
  2. Traverse basis vectors from highest bit to lowest bit.
  3. If XORing the current basis vector increases the answer, perform the XOR.

Because higher bits dominate lower bits in numerical value, greedily improving from the highest bit downward produces the maximum possible XOR.

Step 4: Return the result

The resulting value is the maximum subset XOR and therefore the maximum possible value of X XOR Y.

Why it works

The basis construction produces a set of linearly independent XOR vectors whose span is exactly the set of all subset XOR values obtainable from the original array.

Every subset XOR can be represented as a combination of basis vectors, and every basis combination corresponds to some subset XOR. The greedy reconstruction phase always attempts to set the highest possible bit first. Since higher bits dominate lower bits numerically, this process yields the largest value in the span of the basis. Therefore the algorithm returns the maximum achievable X XOR Y.

Python Solution

from typing import List

class Solution:
    def maxXorSubsequences(self, nums: List[int]) -> int:
        basis = [0] * 31

        for x in nums:
            cur = x

            for bit in range(30, -1, -1):
                if not (cur >> bit) & 1:
                    continue

                if basis[bit]:
                    cur ^= basis[bit]
                else:
                    basis[bit] = cur
                    break

        answer = 0

        for bit in range(30, -1, -1):
            if (answer ^ basis[bit]) > answer:
                answer ^= basis[bit]

        return answer

The implementation uses a 31-element basis because every value is at most 10^9, which fits within 30 bits.

During basis construction, each number is reduced using previously inserted basis vectors. If the number becomes zero, it is linearly dependent and contributes no new information. Otherwise, it introduces a new leading bit and is inserted into the basis.

After the basis is complete, the second loop greedily builds the largest possible XOR value. For each basis vector, we check whether using it increases the current answer. If it does, we keep it.

The final value is the maximum subset XOR, which is exactly the answer required by the problem.

Go Solution

func maxXorSubsequences(nums []int) int {
	basis := make([]int, 31)

	for _, x := range nums {
		cur := x

		for bit := 30; bit >= 0; bit-- {
			if ((cur >> bit) & 1) == 0 {
				continue
			}

			if basis[bit] != 0 {
				cur ^= basis[bit]
			} else {
				basis[bit] = cur
				break
			}
		}
	}

	ans := 0

	for bit := 30; bit >= 0; bit-- {
		if ans^basis[bit] > ans {
			ans ^= basis[bit]
		}
	}

	return ans
}

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

Since nums[i] ≤ 10^9, all computations comfortably fit inside Go's int type on LeetCode platforms. No special overflow handling is required. The basis is stored as a fixed-size slice of length 31, corresponding to bit positions 0 through 30.

Worked Examples

Example 1

Input:

nums = [1, 2, 3]

Build Basis

Number Action Basis
1 Insert at bit 0 {1}
2 Insert at bit 1 {2,1}
3 3 XOR 2 = 1, 1 XOR 1 = 0 unchanged

Basis vectors:

bit 1 -> 2
bit 0 -> 1

Build Maximum XOR

Step Current Answer Vector New Answer
Start 0 - 0
bit 1 0 2 2
bit 0 2 1 3

Result:

3

Example 2

Input:

nums = [5, 2]

Build Basis

Number Action
5 Insert
2 Insert

Basis:

5 (101)
2 (010)

Build Maximum XOR

Step Current Answer Vector New Answer
Start 0 - 0
Use 5 0 5 5
Use 2 5 2 7

Result:

7

Complexity Analysis

Measure Complexity Explanation
Time O(n · 31) Each number is processed across at most 31 bits
Space O(31) Fixed-size XOR basis

Since 31 is a constant, the complexity is effectively linear in the size of the input array.

Even for n = 100000, the algorithm performs only a few million bit operations, which is easily fast enough.

Test Cases

sol = Solution()

assert sol.maxXorSubsequences([1, 2, 3]) == 3      # example 1
assert sol.maxXorSubsequences([5, 2]) == 7         # example 2

assert sol.maxXorSubsequences([0, 0]) == 0         # all zeros
assert sol.maxXorSubsequences([1, 1]) == 1         # duplicate values
assert sol.maxXorSubsequences([2, 2]) == 2         # duplicate powers of two

assert sol.maxXorSubsequences([1, 2]) == 3         # simple combination
assert sol.maxXorSubsequences([1, 2, 4]) == 7      # all independent bits
assert sol.maxXorSubsequences([8, 4, 2, 1]) == 15  # full bit coverage

assert sol.maxXorSubsequences([7, 7, 7]) == 7      # all identical
assert sol.maxXorSubsequences([3, 5, 6]) == 6      # dependent vectors

assert sol.maxXorSubsequences([1000000000, 0]) == 1000000000  # large value
assert sol.maxXorSubsequences([9, 10, 5]) == 15   # mixed values

Test Summary

Test Why
[1,2,3] Official example
[5,2] Official example
[0,0] All values zero
[1,1] Duplicate values
[2,2] Duplicate power of two
[1,2] Small independent basis
[1,2,4] Every bit independent
[8,4,2,1] Maximum combination of distinct bits
[7,7,7] Repeated identical values
[3,5,6] Linear dependency case
[1000000000,0] Large boundary value
[9,10,5] General mixed input

Edge Cases

All Elements Are Zero

Consider:

[0, 0, 0]

Every subset XOR is zero. A buggy implementation might accidentally insert zero into the basis or treat it as an independent vector. The basis construction naturally ignores zeros because they never introduce a leading bit. The returned answer is correctly 0.

Many Duplicate Values

Consider:

[7, 7, 7, 7]

Repeated values are linearly dependent under XOR. A naive basis implementation might store multiple copies and produce incorrect results. During elimination, all redundant copies reduce to zero and are discarded. Only one independent vector remains.

Maximum Answer Requires Combining Several Numbers

Consider:

[1, 2, 4, 8]

The largest element is 8, but the optimal XOR is:

1 XOR 2 XOR 4 XOR 8 = 15

A greedy strategy that simply chooses the largest number would fail. The linear basis correctly explores the entire XOR vector space and finds the globally optimal value 15.

Overlapping Subsequences

The statement explicitly allows overlap. This detail is easy to overlook and fundamentally changes the problem. Because an element may appear in both subsequences, its contribution can be canceled out in X XOR Y. This makes every subset XOR achievable, which is exactly the property that reduces the problem to the classical maximum subset XOR problem. The implementation relies on this observation and therefore handles overlapping choices correctly.