#3681

Maximum XOR of Subsequences

hard · 51.3% accepted · 59 likes · top 40%

array · math · greedy · bit manipulation

⊣ practice⊣ open on leetcode ↗

Description

You are given an integer array nums of length n where each element is a non-negative integer.

Select two subsequences of nums (they may be empty and are allowed to overlap), each preserving the original order of elements, and let:

 - X be the bitwise XOR of all elements in the first subsequence.

 - Y be the bitwise XOR of all elements in the second subsequence.

Return the maximum possible value of X XOR Y.

Note: The XOR of an empty subsequence is 0.

Solution