XOR of all subarray XORs

Given an integer array arr[], consider every possible subarray and compute the bitwise XOR of its elements. Find the bitwise XOR of all these subarray XORs.

Examples :

Input: arr[] = [1, 2]
Output: 0
Explanation: All subarrays and their XORs:
XOR[1] = 1
XOR[2] = 2
XOR[1, 2] = 1 ^ 2 = 3
Final XOR: [1 ^ 2 ^ 3] = 0
Input: arr[] = [1, 2, 4]
Output: 5
Explanation: All subarrays and their XORs:
XOR[1] = 1
XOR[2] = 2
XOR[4] = 4
XOR[1, 2] = 1 ^ 2 = 3
XOR[2, 4] = 2 ^ 4 = 6
XOR[1, 2, 4] = 1 ^ 2 ^ 4 = 7
Final XOR: [1 ^ 2 ^ 4 ^ 3 ^ 6 ^ 7] = 5

Try it on GfG Practice

Table of Content

[Naive Approach] Calculating XOR for Every Possible SubArray - O(n^2) Time and O(1) Space
[Expected Approach] Using Subarray Contribution and XOR Property - O(n) Time and O(1) Space

[Naive Approach] Calculating XOR for Every Possible SubArray - O(n²) Time and O(1) Space

The idea is to consider every possible subarray of the array. For each subarray, we calculate the XOR of its elements. Finally, we XOR all these subarray results together to get the final answer.

C++

//Driver Code Starts
#include <iostream>
#include <vector>
using namespace std;

//Driver Code Ends

int subarrayXor(vector<int>& arr) {
    int result = 0;
    int n = arr.size();

    // iterate over all subarrays
    for (int i = 0; i < n; i++) {
        int tempXor = 0;
        for (int j = i; j < n; j++) {
            
            // XOR elements of current subarray
            tempXor ^= arr[j];   
            
            // XOR with final result
            result ^= tempXor;   
        }
    }

    return result;
}

//Driver Code Starts

int main() {
    vector<int> arr = {1, 2, 4};
    cout << subarrayXor(arr) << endl;

    return 0;
}

//Driver Code Ends

Java

//Driver Code Starts
class GFG {

//Driver Code Ends

    static int subarrayXor(int[] arr) {
        int result = 0;
        int n = arr.length;

        // iterate over all subarrays
        for (int i = 0; i < n; i++) {
            int tempXor = 0;
            for (int j = i; j < n; j++) {
         
                // XOR elements of current subarray
                tempXor ^= arr[j];
                
                // XOR with final result
                result ^= tempXor;
            }
        }

        return result;
    }

//Driver Code Starts

    public static void main(String[] args) {
        int[] arr = {1, 2, 4};
        System.out.println(subarrayXor(arr));
    }
}

//Driver Code Ends

Python

def subarrayXor(arr):
    result = 0
    n = len(arr)

    # iterate over all subarrays
    for i in range(n):
        tempXor = 0
        for j in range(i, n):
        
            # XOR elements of current subarray
            tempXor ^= arr[j]
            
            # XOR with final result
            result ^= tempXor

    return result


#Driver Code Starts
if __name__ == '__main__':
    arr = [1, 2, 4]
    print(subarrayXor(arr))

#Driver Code Ends

//Driver Code Starts
using System;

class GFG {
    
//Driver Code Ends

    static int subarrayXor(int[] arr) {
        int result = 0;
        int n = arr.Length;

        // iterate over all subarrays
        for (int i = 0; i < n; i++) {
            int tempXor = 0;
            for (int j = i; j < n; j++) {
               
                // XOR elements of current subarray
                tempXor ^= arr[j];

                // XOR with final result
                result ^= tempXor;
            }
        }

        return result;
    }

//Driver Code Starts

    static void Main() {
        int[] arr = {1, 2, 4};
        Console.WriteLine(subarrayXor(arr));
    }
}

//Driver Code Ends

JavaScript

function subarrayXor(arr) {
    let result = 0;
    let n = arr.length;

    // iterate over all subarrays
    for (let i = 0; i < n; i++) {
        let tempXor = 0;
        for (let j = i; j < n; j++) {
            // XOR elements of current subarray
            tempXor ^= arr[j];

            // XOR with final result
            result ^= tempXor;
        }
    }

    return result;
}


//Driver Code Starts
// Driver code
let arr = [1, 2, 4];
console.log(subarrayXor(arr));

//Driver Code Ends

Output

[Expected Approach] Using Subarray Contribution and XOR Property - O(n) Time and O(1) Space

Each element arr[i] (0-based index) appears in all subarrays that start at or before index i and end at or after index i. There are (i + 1) choices for the starting index (from 0 to i) and (n - i) choices for the ending index (from i to n-1), so the total number of subarrays containing arr[i] is (i + 1) * (n - i).

In the XOR of all subarrays, an element only contributes if it appears an odd number of times, because XORing a number an even number of times cancels it out. Therefore, we include arr[i] in the final XOR only if both (i + 1) and (n - i) are odd, which ensures the total count is odd.

C++

//Driver Code Starts
#include <iostream>
#include <vector>
using namespace std;

//Driver Code Ends

int subarrayXor(vector<int>& arr) {
    int result = 0;
    int n = arr.size();

    for (int i = 0; i < n; i++) {
        
        // Check if (i+1) and (n-i) are both odd
        if ((i + 1) % 2 != 0 && (n - i) % 2 != 0) {
            
            // Include element in final XOR
            result ^= arr[i];  
        }
    }

    return result;
}

//Driver Code Starts

int main() {
    vector<int> arr = {1, 2, 4};
    cout << subarrayXor(arr) << endl; 
    return 0;
}

//Driver Code Ends