Maximum Subset XOR

Problem Overview

The maximum XOR over any subset equals the maximum value obtainable from the linear XOR-span of the array.

Intuition

The maximum XOR over any subset equals the maximum value obtainable from the linear XOR-span of the array. Gaussian elimination from the highest bit builds a basis: each bit that can still be introduced gets one pivot vector, and all other numbers lose that bit. Then greedily fold basis vectors into the answer whenever XOR increases it.

Algorithm

1Set index = 0. For bit = 31 down to 0:
2 Find the first arr[i] (i >= index) with that bit set; if none, continue.
3 Swap it into position index.
4 XOR arr[index] into every other element that still has that bit set.
5 Increment index (basis size).
6Initialize ans = 0. For each basis vector, set ans = max(ans, ans XOR vector).
7Return ans.

Example Walkthrough

Input: arr = [2, 4, 5]

1. Binary: 010, 100, 101.
2. After elimination the basis can represent combinations whose XOR reaches 7 (2 XOR 5).
3. Greedy pass yields ans = 7.

Output: 7

Common Pitfalls

• Process bits from high to low so the basis prioritizes higher bits.
• Empty subset XOR is 0, but the greedy max with non-empty options still covers the best non-empty subset when positives help.
• In-place XORs modify arr - that is intended for the basis construction.
• Do not confuse with maximum XOR of two numbers (that is a different trie problem).

Maximum Subset XOR.java

Java


class Solution {

    // Approach: Build a linear XOR basis with Gaussian elimination from MSB to
    // LSB. For each bit, pivot on a number with that bit set, then clear the bit
    // from every other number. Greedily XOR basis vectors into the answer when
    // that increases it, yielding the maximum subset XOR.
    // Complexity: O(32 * n) time and O(1) extra space (in-place on arr).
    public int maxSubsetXOR(int[] arr) {
        int n = arr.length;
        int index = 0;
        // Traverse from highest bit to lowest bit
        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;
                }
            }

            if (maxIndex == -1) {
                continue;
            }

            // Swap
            int temp = arr[index];
            arr[index] = arr[maxIndex];
            arr[maxIndex] = temp;
            // Eliminate current bit from all other elements
            for (int i = 0; i < n; i++) {
                if (i != index && (((arr[i] >> bit) & 1) == 1)) {
                    arr[i] ^= arr[index];
                }
            }
            index++;
        }

        // Build maximum XOR
        int ans = 0;
        for (int i = 0; i < index; i++) {
            ans = Math.max(ans, ans ^ arr[i]);
        }

        return ans;
    }
}

Was this solution helpful?