Logo
IconChallenge
Icon
IconProblem
IconSolutions
IconSubmissions

Maximum XOR of Subsequences

XPChallenge Points: 30
levelLevel: Hard

You are given an integer array nums of length n (non-negative values). Choose two subsequences (each can be empty and may overlap). Let X be the XOR of the first subsequence and Y be the XOR of the second subsequence. Return the maximum value of X XOR Y.
Note: The XOR of an empty subsequence is 0.

Key insight: The set of all subsequence XORs equals the set of all subset XORs, which forms a linear subspace over GF(2). Since 0 (empty subsequence) is allowed,

maxX,Y(XY)  =  maxZsubset-XORsZ,\max_{X,Y} (X \oplus Y) \;=\; \max_{Z\in\text{subset-XORs}} Z,

i.e., the answer is simply the maximum subset XOR. Compute it via a XOR-basis (Gaussian elimination over bits).

Example 1:

Input: nums = [4, 1, 2]

Output: 7

Explanation:

Pick subsequences: - First: [4, 2] → XOR X = 4 ⊕ 2 = 6 - Second: [1] → XOR Y = 1 X ⊕ Y = 6 ⊕ 1 = 7 (maximum achievable).

Example 2:

Input: nums = [8, 8, 8]

Output: 8

Explanation:

All subset XORs are {0, 8}. Choose: - First: [8] → X = 8 - Second: [] → Y = 0 X ⊕ Y = 8 ⊕ 0 = 8 (maximum).

to Continue
like
dislike

Accepted:

Submission:

IconReport an issue
Icon
IconCode
IconYou need toto run or submitYou need toto run or submit
IconTest Case
IconTest Result