用异或和求数组的子数组数

Question

给你下面的数组A，我们需要用XOR和X分别计算子数组的总数，子数组应该满足条件(X+1) = (X^1)。这是我的解决方案，


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))

但是这个解决方案的时间复杂度为 O(n^3)，超过了我对大型数组集的时间限制。有什么方法可以优化此代码以降低时间复杂度吗？

Answer 1

操作X ^ 1 更改数字的最后一位。所以 ****1 变成 ****0 反之亦然。

所以我们可以看到对于X的奇数值，X ^ 1的值小于X，但是对于偶数X的值X ^ 1 比 X 大一 - 正是我们需要的。

现在我们可以用偶数异或和计算子数组了。请注意，我们记住了从零索引开始的子数组已经有多少个奇数和偶数 xorsum：

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

Answer 2

条件(X+1) = (X^1)就是说X必须是偶数。因此，只需使用前缀异或计数来计算偶数异或。花费 O(n) 时间和 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!（有测试）

用异或和求数组的子数组数

find the number of subarrays of an array with XOR sum

python

algorithm

performance

time-complexity