Last Updated: 29 Sep, 2025
Maximum XOR Subset
Moderate
Asked in company
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.
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.
