Maximum XOR Subset

Moderate

0/80

0 upvote

Asked in company

Problem statement

You are given an array arr of N positive integers. Your task is to find the maximum possible XOR value that can be obtained by selecting any non-empty subset of elements from the array and taking their bitwise XOR.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer N, the size of the array.

The second line contains N space-separated integers, representing the elements of the array arr.

Output Format:

Print a single integer representing the maximum achievable XOR value.

Note:

A brute-force approach of checking all 2^N - 1 non-empty subsets is too slow.

The key to an optimal solution is to first construct an XOR basis from the given array. An XOR basis is a minimal set of numbers from which all possible XOR sums of the original array's subsets can be generated.

Sample Input 1:

3
2 4 5

Sample Output 1:

Explanation for Sample 1:

The subsets and their XOR values are:
- `{2}` -> 2
- `{4}` -> 4
- `{5}` -> 5
- `{2, 4}` -> 2 ^ 4 = 6
- `{2, 5}` -> 2 ^ 5 = 7
- `{4, 5}` -> 4 ^ 5 = 1
- `{2, 4, 5}` -> 2 ^ 4 ^ 5 = 3
The maximum value among these is 7.

Sample Input 2:

3
8 1 2

Sample Output 2:

Explanation for Sample 2:

The optimal subset is `{8, 1, 2}`. The XOR sum is `8 ^ 1 ^ 2 = 11`.

Expected Time Complexity:

The expected time complexity is O(N * log(max(arr))), as building the basis takes N iterations, and each insertion involves a loop proportional to the number of bits.

Constraints:

1 <= N <= 10^5
1 <= arr[i] <= 10^9

Time limit: 1 sec

Approaches (1)

Approach 1

Bit Manipulation

Time Complexity

Space Complexity

(100% EXP penalty)

Maximum XOR Subset

Console