Split the Array

Given an array arr[] of integers, the task is to count the number of ways to split given array elements into two disjoint groups such that the XOR of elements of each group is equal.
Note: The answer could be very large so print it by doing modulo with 10⁹ + 7. 

Examples:

Input : arr[] = [1, 2, 3]
Output : 3
Explanation: {(1),(2, 3)}, {(2),(1, 3)}, {(3),(1, 2)} are three ways with equal XOR value of two groups.

Input : arr[] = [5, 2, 3, 2]
Output : 0
Explanation: No way to split into  two groups whose XOR is equal.

Expected Time Complexity: O(n).
Expected Auxiliary Space: O(1).

Constraints:
1<=arr.size()<=10⁶
1<=arr[i]<=10⁶

Approach 01:

class Solution {
  public:
    int countgroup(vector<int>& arr) {
        int xorResult = 0;

        for (int num : arr) {
            xorResult ^= num;  // Compute the XOR of all elements
        }

        // Return 2^(n-1) - 1 if XOR is 0, otherwise return 0
        return (xorResult == 0) ? (1 << (arr.size() - 1)) - 1 : 0; 
    }
};

class Solution:
    def countgroup(self, arr):
        xorResult = 0

        for num in arr:
            xorResult ^= num  # Compute the XOR of all elements

        # Return 2^(n-1) - 1 if XOR is 0, otherwise return 0
        return (2 ** (len(arr) - 1) - 1) if xorResult == 0 else 0

Time Complexity

• XOR Calculation:

  The function iterates through the input array once to compute the XOR of all elements. This operation takes \(O(n)\), where \(n\) is the number of elements in the array.

• Final Calculation:

  After computing the XOR, the function checks if the result is zero and performs a bit shift operation. These operations take constant time, \(O(1)\).

• Overall Time Complexity:

  The overall time complexity is \(O(n)\).

Space Complexity

• Auxiliary Space:

  No additional data structures are used that grow with the input size. Only a few variables are used to store intermediate values.

• Overall Space Complexity:

  The overall space complexity is \(O(1)\).