使用Python查找奇数和子数组数量的程序

假设我们有一个数组arr。我们必须找到奇数和的子数组的数量。如果答案过大，则返回结果模10^9+7。

因此，如果输入类似于arr = [8,3,7]，则输出将为3，因为所有子数组为[[8],[3],[7],[8,3],[3,7],[8,3,7]]。现在它们的和值为[8,3,7,11,10,18]，所以有三个奇数和值[3,7,11]。

为了解决这个问题，我们将遵循以下步骤：

• freq := 一个包含两个元素1和0的列表

• ans := 0

• prefix := 0

• 对于arr中的每个x，执行：

  • prefix := prefix + x

  • ans := ans + freq[1 XOR prefix AND 1]

  • freq[prefix AND 1] := freq[prefix AND 1] + 1

• 返回ans mod (10^9+7)

让我们来看下面的实现，以便更好地理解：

示例

 在线演示

def solve(arr):
   freq = [1, 0]
   ans = prefix = 0
   for x in arr:
      prefix += x
      ans += freq[1 ^ prefix&1]
      freq[prefix &s; 1] += 1
   return ans % (10**9+7)
arr = [8,3,7]
print(solve(arr))

输入

[8,3,7]

输出

3

Arnab Chakraborty

更新于：2021年5月29日

156 次浏览

启动您的职业生涯

通过完成课程获得认证

开始