Problem Statement
You are given an array arr[]. You can choose any subset of the array (including a subset containing one element or all elements). Your task is to find the maximum possible XOR of the chosen subset.
Example 1
Input
arr = [2, 4, 5]
Possible XORs
{} = 0
{2} = 2
{4} = 4
{5} = 5
{2,4} = 6
{2,5} = 7 <- Maximum
{4,5} = 1
{2,4,5} = 3
Output
7
Example 2
Input
arr = [9, 8, 5]
Output
13
Explanation
8 XOR 5 = 13
Naive Approach
Generate every possible subset and calculate its XOR.
This works only for very small arrays.
Since n can be 100000, we need a much faster solution.
Efficient Approach (XOR Basis / Gaussian Elimination)
The idea is very similar to Gaussian Elimination used in mathematics.
Instead of eliminating numbers using addition and subtraction, we eliminate bits using the XOR operation.
The goal is to build a set of independent numbers called the XOR Basis.
Key Observation
Suppose we have
2 = 010
4 = 100
5 = 101
Notice:
5 XOR 4 = 001
Now our basis becomes
100
010
001
Using these three numbers, we can generate every XOR combination.
The maximum possible XOR is
100
010
001
-------
111 = 7
Algorithm
Starting from the most significant bit (31st bit) to the least significant bit:
Step 1
Find a number whose current bit is set.
Example
Bit = 4
16 = 10000
20 = 10100
9 = 01001
Choose one number having bit 4 set.
Step 2
Move that number to the current position.
This becomes our pivot.
Step 3
Remove that bit from every other number.
If another number also has that bit,
number ^= pivot
This clears the highest set bit.
Repeat for every bit.
Eventually every basis element has a unique highest set bit.
Dry Run
Input
arr = [2,4,5]
Binary
2 = 010
4 = 100
5 = 101
Processing Bit 2 (Value = 4)
Pivot
100
Eliminate from others
101 XOR 100 = 001
Now
100
010
001
Processing Bit 1 (Value = 2)
Pivot
010
No elimination needed.
Processing Bit 0 (Value = 1)
Pivot
001
Finished.
Final basis
100
010
001
Maximum XOR
100
010
001
-------
111 = 7
Answer = 7
Code
class Solution {
public int maxSubsetXOR(int[] arr) {
int n = arr.length;
// Position where next basis element will be placed
int index = 0;
// Traverse every bit from MSB to LSB
for (int bit = 31; bit >= 0; bit--) {
int maxIndex = -1;
// Find an element with current bit set
for (int i = index; i < n; i++) {
if (((arr[i] >> bit) & 1) == 1) {
maxIndex = i;
break;
}
}
// No element has this bit
if (maxIndex == -1)
continue;
// Bring pivot to current position
int temp = arr[index];
arr[index] = arr[maxIndex];
arr[maxIndex] = temp;
// Remove current bit from every other element
for (int i = 0; i < n; i++) {
if (i != index &&
((arr[i] >> bit) & 1) == 1) {
arr[i] ^= arr[index];
}
}
index++;
}
// XOR of basis gives maximum subset XOR
int result = 0;
for (int num : arr)
result ^= num;
return result;
}
}
Code Explanation
1. Store Array Size
int n = arr.length;
Stores the number of elements.
2. Basis Index
int index = 0;
This indicates where the next pivot (basis element) will be placed.
Initially
index = 0
After first pivot
index = 1
and so on.
3. Traverse Every Bit
for(int bit = 31; bit >= 0; bit--)
We process bits from the most significant bit to the least significant bit.
Why?
Because larger bits contribute more to the final XOR.
4. Find Pivot
int maxIndex = -1;
for(int i=index;i<n;i++){
if(((arr[i]>>bit)&1)==1){
maxIndex=i;
break;
}
}
Find any number that has the current bit set.
Example
Bit = 2
4 = 100
5 = 101
2 = 010
We can choose
100
or
101
Both work.
5. Skip if Bit Doesn't Exist
if(maxIndex==-1)
continue;
No number contains this bit.
Move to the next smaller bit.
6. Swap Pivot
int temp=arr[index];
arr[index]=arr[maxIndex];
arr[maxIndex]=temp;
Bring the pivot to the front of the remaining array.
7. Eliminate Current Bit
for(int i=0;i<n;i++){
if(i!=index &&
((arr[i]>>bit)&1)==1){
arr[i]^=arr[index];
}
}
Suppose
Pivot = 100
Another =101
Then
101
XOR
100
----
001
Now only one number contains that highest bit.
8. Move to Next Basis Position
index++;
Current pivot is fixed.
Move to the next position.
9. Calculate Answer
int result=0;
for(int x:arr)
result^=x;
After elimination, every remaining non-zero element is an independent basis vector. XORing all basis vectors produces the largest possible subset XOR because each basis vector contributes a unique highest set bit.
Why Does XOR of Basis Give Maximum?
Suppose the basis is
1000
0100
0010
0001
Every basis vector has a unique leading bit.
Including all of them gives
1000
0100
0010
0001
---------
1111
No other subset can produce a larger binary value because removing any basis vector would unset one of these highest bits.
Complexity Analysis
| Complexity | Value |
|---|
| Time | O(32 × n) ≈ O(n) |
| Space | O(1) |
Since integers have only 32 bits, the algorithm processes each bit once and scans the array for each bit, making it efficient even for very large arrays.
Key Takeaways
Brute force (2ⁿ) is infeasible for large n.
Build a XOR Basis using Gaussian elimination over bits.
Process bits from the most significant to the least significant.
Each pivot owns a unique highest set bit.
Eliminate that bit from all other numbers using XOR.
XOR of all basis elements gives the maximum subset XOR.
Time Complexity: O(32 × n) ≈ O(n)
Space Complexity: O(1)
Summary
This article explained how to find the maximum subset XOR efficiently using the XOR Basis (Gaussian Elimination over bits) technique. Instead of checking every possible subset, the algorithm constructs a set of independent basis vectors by eliminating duplicate highest set bits using XOR. Once the basis is built, XORing all basis elements produces the maximum possible subset XOR. This approach runs in O(32 × n) ≈ O(n) time with O(1) extra space, making it suitable even for very large arrays.