使用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 次瀏覽

啟動您的職業生涯

透過完成課程獲得認證

開始