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,
i.e., the answer is simply the maximum subset XOR. Compute it via a XOR-basis (Gaussian elimination over bits).
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).
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).
Accepted:
Submission: