1407. XOR Basis — Gaussian Elimination over GF(2)

Given an array of non-negative integers, return the maximum XOR value obtainable by XOR-ing together any subset of the elements (the empty subset gives 0). Build a linear basis over GF(2) by Gaussian elimination and combine its vectors greedily.

Input: A JSON object {"nums": [<non-negative integers>]}.

Output: Return the maximum achievable subset XOR.

Examples

Input: {"nums":[1,2,3,4,5,6,7,8]}
Output: 15
Explanation: The best subset XOR is 15.

Input: {"nums":[8,4,2]}
Output: 14
Explanation: Combining all three gives 14.

Constraints

• 1 <= len(nums) <= 10^5
• 0 <= nums[i] < 2^60

Asked by