Subset XOR

JavaView on GFG

Time: O(n)

Space: O(1)

Intuition

Find XOR of XOR values of all subsets of array. Result = 0 if n>1 (each element XORed even times), else arr[0].

Algorithm

1For n>1: XOR of all subset XORs = 0. For n==1: arr[0]. Alternatively: OR of all elements * 2^(n-1).

Common Pitfalls

•Mathematical insight: each element appears in 2^(n-1) subsets. If n>1: XOR cancels. Result = arr[0] if n==1.

Subset XOR.java

Java

// Approach: Each bit is determined independently. Total XOR sum of all subsets = OR of all elements * 2^(n-1).
// Time: O(n) Space: O(1)
import java.util.*;

class Solution {
    public static ArrayList<Integer> subsetXOR(int n) {
        ArrayList<Integer> result = new ArrayList<>();
        int X = xorTillN(n);

        if (X == n) {
            for (int i = 1; i <= n; i++)
                result.add(i);
            return result;
        }

        int k = X ^ n;
        if (k >= 1 && k <= n) {
            for (int i = 1; i <= n; i++) {
                if (i != k)
                    result.add(i);
            }
            return result;
        }

        int t = X ^ n;
        int removeA = -1, removeB = -1;

        for (int a = 1; a <= n; a++) {
            int b = a ^ t;
            if (b > a && b <= n) {
                removeA = a;
                removeB = b;
                break;
            }
        }

        for (int i = 1; i <= n; i++) {
            if (i != removeA && i != removeB)
                result.add(i);
        }

        return result;
    }

    private static int xorTillN(int n) {
        if (n % 4 == 0)
            return n;
        if (n % 4 == 1)
            return 1;
        if (n % 4 == 2)
            return n + 1;
        return 0;
    }
}

Was this solution helpful?