Maximum Subset XOR (Java)

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

Code

arr = [2, 4, 5]

Possible XORs

Code

{} = 0
{2} = 2
{4} = 4
{5} = 5
{2,4} = 6
{2,5} = 7   <- Maximum
{4,5} = 1
{2,4,5} = 3

Output

Code

Example 2

Input

Code

arr = [9, 8, 5]

Output

Code

Explanation

Code

8 XOR 5 = 13

Naive Approach

Generate every possible subset and calculate its XOR.

Number of subsets = 2ⁿ
Time Complexity = O(2ⁿ × n)

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

Code

2 = 010
4 = 100
5 = 101

Notice:

Code

5 XOR 4 = 001

Now our basis becomes

Code

100
010
001

Using these three numbers, we can generate every XOR combination.

The maximum possible XOR is

Code

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

Code

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,

Code

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

Code

arr = [2,4,5]

Binary

Code

2 = 010
4 = 100
5 = 101

Processing Bit 2 (Value = 4)

Pivot

Code

Eliminate from others

Code

101 XOR 100 = 001

Now

Code

100
010
001

Processing Bit 1 (Value = 2)

Pivot

Code

No elimination needed.

Processing Bit 0 (Value = 1)

Pivot

Code

Finished.

Final basis

Code

100
010
001

Maximum XOR

Code

100
010
001
-------
111 = 7

Answer = 7

Code

Java

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

Java

int n = arr.length;

Stores the number of elements.

2. Basis Index

Java

int index = 0;

This indicates where the next pivot (basis element) will be placed.

Initially

Code

index = 0

After first pivot

Code

index = 1

and so on.

3. Traverse Every Bit

Java

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

Java

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

Code

4 = 100
5 = 101
2 = 010

We can choose

Code

Both work.

5. Skip if Bit Doesn't Exist

Java

if(maxIndex==-1)
    continue;

No number contains this bit.

Move to the next smaller bit.

6. Swap Pivot

Java

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

Java

for(int i=0;i<n;i++){

    if(i!=index &&
       ((arr[i]>>bit)&1)==1){

        arr[i]^=arr[index];
    }
}

Suppose

Code

Pivot = 100

Another =101

Then

Code

101
XOR
100
----
001

Now only one number contains that highest bit.

8. Move to Next Basis Position

Java

index++;

Current pivot is fixed.

Move to the next position.

9. Calculate Answer

Java

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

Code

Every basis vector has a unique leading bit.

Including all of them gives

Code

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.