使用 XOR 求和查找数组的子数组数 [英] find the number of subarrays of an array with XOR sum

问题描述

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

<预><代码>def getTotalXorOfSubarrayXors(arr, N):X = 0计数 = 0对于范围(0，N)中的我:对于范围内的 j (i, N):对于范围内的 k(i, j + 1):X = X ^ arr[k]如果 X+1 == X^1:计数 +=1X = 0返回计数arr = [3, 5, 2, 4, 6]N = len(A)打印(getTotalXorOfSubarrayXors(A，N))

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

解决方案

条件 (X+1) = (X^1) 只是意味着 X 必须是偶数.因此，只需使用 prefix-xor-counts 计算偶数异或.花费 O(n) 时间和 O(1) 空间.

def getTotalXorOfSubarrayXors(A, _):X = 0计数 = [1, 0]总计 = 0对于 A 中的 a:X ^= a &1总计 += 计数[X]计数[X] += 1总回报

在线试用！(带测试)

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?

解决方案

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)

这篇关于使用 XOR 求和查找数组的子数组数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！