Subset XOR

JavaView on GFG

Time: O(n)

Space: O(1)

Problem Overview

Find XOR of XOR values of all subsets of array.

See our study guide for structured GFG and LeetCode practice.

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?