1. Introduction
The XOR of All Subarray XORs is a mathematical and bit-manipulation problem.
In this problem, we are given an integer array. We need to find all possible non-empty contiguous subarrays, calculate the XOR of each subarray, and finally calculate the XOR of all those results.
At first, this problem looks like we need to generate every possible subarray and calculate its XOR.
However, generating all subarrays takes O(n²) time.
We can solve this problem efficiently in O(n) time and O(1) auxiliary space using a mathematical observation.
2. Problem Statement
Given an integer array arr[], find the XOR of the XOR values of all possible non-empty subarrays.
Example 1:
Input: arr = [1, 2, 3]
Output: 2
Explanation:
All possible non-empty subarrays are:
| Subarray | XOR |
|---|
| [1] | 1 |
| [1, 2] | 3 |
| [1, 2, 3] | 0 |
| [2] | 2 |
| [2, 3] | 1 |
| [3] | 3 |
Final XOR:
1 ^ 3 ^ 0 ^ 2 ^ 1 ^ 3
= 2
Example 2:
Input: arr = [1, 2]
Output: 0
All possible subarrays:
[1] → 1
[1, 2] → 3
[2] → 2
Final XOR:
1 ^ 3 ^ 2 = 0
3. Understanding the XOR Operator
Before solving the problem, let's understand the XOR operator.
XOR is a bitwise operator represented by ^ in C#.
It returns 1 when two corresponding bits are different and 0 when they are the same.
Important XOR properties:
Property 1: Same number XOR itself becomes zero.
5 ^ 5 = 0
Property 2: XOR with zero returns the same number.
5 ^ 0 = 5
Property 3: XOR is associative.
(1 ^ 2) ^ 3 = 1 ^ (2 ^ 3)
Property 4: XOR is commutative.
1 ^ 2 = 2 ^ 1
These properties help us simplify the problem.
4. Brute Force Approach
The simplest approach is to generate every possible non-empty subarray and calculate its XOR.
For example:
arr = [1, 2, 3]
We use two loops to select the starting and ending positions.
class Solution
{
public int subarrayXor(int[] arr)
{
int n = arr.Length;
int result = 0;
for (int i = 0; i < n; i++)
{
int xor = 0;
for (int j = i; j < n; j++)
{
xor ^= arr[j];
result ^= xor;
}
}
return result;
}
}
How does it work?
- The outer loop selects the starting index.
- The inner loop selects the ending index.
xor calculates the XOR of the current subarray.result stores the XOR of all subarray XOR values.
Complexity:
- Time Complexity: O(n²)
- Auxiliary Space: O(1)
This approach works, but it is not efficient enough for the expected O(n) complexity.
5. Optimized Approach – Mathematical Observation
Instead of generating all subarrays, let's observe how many times each element appears in all possible subarrays.
Consider:
arr = [1, 2, 3]
The subarrays are:
[1]
[1, 2]
[1, 2, 3]
[2]
[2, 3]
[3]
Now count how many times each element appears.
| Element | Number of occurrences |
|---|
| 1 | 3 |
| 2 | 4 |
| 3 | 3 |
Because XOR cancels repeated values:
1 ^ 1 ^ 1 = 1
2 ^ 2 ^ 2 ^ 2 = 0
3 ^ 3 ^ 3 = 3
Therefore:
Final result = 1 ^ 3 = 2
We can conclude:
- Elements appearing an even number of times disappear.
- Elements appearing an odd number of times remain.
Mathematical Formula
For an element at index i, the number of subarrays containing that element is:
\[ Count = (i+1)\times(n-i) \]
Why?
There are two choices:
- Starting index can be anywhere from
0 to i, giving i + 1 choices. - Ending index can be anywhere from
i to n - 1, giving n - i choices.
Therefore:
\[ Count(i)=(i+1)(n-i) \]
An element contributes to the final answer only when its occurrence count is odd.
6. Important Mathematical Observation
Let's examine two cases.
Case 1: Array length is even
When n is even, one of the two factors (i + 1) and (n - i) is always even.
Therefore, their product is always even.
That means every element appears an even number of times.
So the final answer is:
\[ Answer=0 \]
Case 2: Array length is odd
When n is odd, both factors are odd only when i is even.
Therefore, only elements at even indices contribute to the answer.
For example:
arr = [1, 2, 3, 4, 5]
Even indices:
Index: 0 1 2 3 4
Array: 1 2 3 4 5
^ ^ ^
Final result:
1 ^ 3 ^ 5 = 7
7. Optimized C# Solution
Expected Solution
class Solution
{
public int subarrayXor(int[] arr)
{
int n = arr.Length;
// If array length is even, return 0
if (n % 2 == 0)
return 0;
int result = 0;
// XOR elements at even indices
for (int i = 0; i < n; i += 2)
{
result ^= arr[i];
}
return result;
}
}
8. Step-by-Step Code Explanation
Step 1: Find the array length
int n = arr.Length;
This gets the total number of elements in the array.
Step 2: Check whether the array length is even
if (n % 2 == 0)
return 0;
If the array length is even, every element appears an even number of times across all possible subarrays.
Therefore, all elements cancel out during XOR.
We can immediately return 0.
Step 3: Initialize the result
int result = 0;
This variable stores the final XOR value.
Initially, it is zero because XOR with zero does not change the value.
Step 4: Traverse only even indices
for (int i = 0; i < n; i += 2)
{
result ^= arr[i];
}
This is the most important part of the solution.
We start from index 0 and increment i by 2.
So the loop visits:
0, 2, 4, 6, 8 ...
Only elements at these positions contribute to the final answer when the array length is odd.
Step 5: Return the result
return result;
Returns the XOR of all elements at even indices.
9. Complete Dry Run
Input:
arr = [1, 2, 3, 4, 5]
Array length:
n = 5
Since 5 % 2 != 0, continue.
Initially:
result = 0
Loop execution:
| Iteration | i | arr[i] | Calculation | Result |
|---|
| 1 | 0 | 1 | 0 ^ 1 | 1 |
| 2 | 2 | 3 | 1 ^ 3 | 2 |
| 3 | 4 | 5 | 2 ^ 5 | 7 |
Final output:
7
Output: 7
10. Complexity Analysis
| Approach | Time Complexity | Auxiliary Space |
|---|
| Brute Force | O(n²) | O(1) |
| Optimized | O(n) | O(1) |
Time Complexity: O(n)
We traverse only the even-indexed elements. This takes at most O(n) time.
Auxiliary Space: O(1)
We use only two variables, n and result. No additional arrays or collections are required.
11. Important Interview Questions
Q1. Why do we return zero when the array length is even?
Because every element appears in an even number of subarrays. XOR of an even number of identical values becomes zero.
Q2. Why do we consider only even indices when the array length is odd?
Because the occurrence count (i + 1) * (n - i) is odd only when both factors are odd. For odd n, this happens at even indices.
Q3. Why don't we generate all possible subarrays?
Generating all subarrays takes O(n²) time. Mathematical observation allows us to calculate the answer directly in O(n).
Q4. Does this solution work with zero and negative integers?
Yes, the XOR logic works with integer values, including zero and negative integers in C#. The given problem constraints, however, specify non-negative values.
12. Key Takeaways
- Understand XOR properties before solving bit-manipulation problems.
- Repeated identical values cancel when they occur an even number of times.
- Count how many times each element contributes to the final result.
- Use the formula
(i + 1) * (n - i) to count subarrays containing an element. - If array length is even, return zero.
- If array length is odd, XOR only the elements at even indices.
Join the conversation! Your thoughts help the community grow.