Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

java

How to find the XOR of all subarray XORs

Ravi

Problem statement

Find the XOR of all the subarray XORs for an array of integers, where subarray XOR is achieved by XORing all of its members in the subarray.

Example 1: With an input of arr = [54, 3, 2, 1], we want to receive an output of 0

Example 2: With an input of arr = [3, 2, 1], we want to receive an output of 2

Solution

A simple solution is to find all the subarrays for the given array, find the XOR for each subarray, and finally, find the XOR of all subarray XORs.

The time complexity of this would be O(N3) and its space complexity would be O(1).

Code

public class Main{
    
    static int xorOfSubarrayXors(int[] arr){
        int res = 0;

        for (int i = 0; i < arr.length; i++)
            for (int j = i; j < arr.length; j++)
                for (int k = i; k <= j; k++)
                    res = res ^ arr[k];

        return res;
    }

    public static void main(String[] args) {
        int[] arr = {3, 2, 1};

        System.out.println("The XOR of all subarray xors is " + xorOfSubarrayXors(arr));
    }
}
Code for XOR of Subarrays

Explanation

  • Lines 3–12: We define the xorOfSubarrayXors() method to find the XOR of all the subarray XORS. There are three nested loops in the method.

    • The first for loop, for (int i = 0; i < arr.length; i++), is used as a starting point of the subarrays.
    • The second for loop, for (int j = i; j < arr.length; j++), is used as the ending point of the subarrays.
    • The third for loop, for (int k = i; k <= j; k++), is used to find the XOR of the subarray.
  • Line 15: We define an array arr.

  • Line 16: We call the xorOfSubarrayXors() method with arr as the parameter.

RELATED TAGS

java
RELATED COURSES

View all Courses

Keep Exploring