python - find the number of subarrays of an array with XOR sum

Question

You are given the following array A, We need to calculate the total number of sub-arrays with XOR sum X were, The sub-array should satisfy the conditions (X+1) = (X^1). Here is my solution,

def getTotalXorOfSubarrayXors(arr, N):
    X = 0
    count = 0
    for i in range(0, N):
      for j in range(i, N):
        for k in range(i, j + 1):
          X = X ^ arr[k]
        if X+1 == X^1:
         count +=1
        X = 0
    return count

arr = [3, 5, 2, 4, 6]
N = len(A)
print(getTotalXorOfSubarrayXors(A, N))

But this solution has a time complexity of O(n^3) which exceeds my time limit for a large set of arrays. Is there is any way I can optimize this code to have less time complexity?

Answer 1

Operation X ^ 1 changes the last bit of a number. So ****1 becomes ****0 and vice versa.

So we can see that for odd values of X value of X ^ 1 is less than X, but for even X's value X ^ 1 is larger by one than X - just what we need.

Now we can count subarrays with even xor-sum. Note that we remember how many odd and even xorsums we already have for subarrays starting from zero index:

def Xors(arr, N):
    oddcnt = 0
    evencnt = 0
    res = 0
    x = 0
    for p in arr:
        x ^= p
        if (x % 2):
            res += oddcnt
            oddcnt += 1
        else:
            evencnt += 1
            res += evencnt
    return res