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

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?

CodePudding user response：

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

CodePudding user response：

The condition (X 1) = (X^1) just means X must be even. So just count the even xors by using prefix-xor-counts. Takes O(n) time and O(1) space.

def getTotalXorOfSubarrayXors(A, _):
    X = 0
    counts = [1, 0]
    total = 0
    for a in A:
        X ^= a & 1
        total  = counts[X]
        counts[X]  = 1
    return total

Try it online! (with tests)