Question

1524. Number of Sub-arrays With Odd Sum

中文文档

Description

Given an array of integers arr, return _the number of subarrays with an odd sum_.

Since the answer can be very large, return it modulo 109 + 7.

 

Example 1:

Input: arr = [1,3,5]
Output: 4
Explanation: All subarrays are [[1],[1,3],[1,3,5],[3],[3,5],[5]]
All sub-arrays sum are [1,4,9,3,8,5].
Odd sums are [1,9,3,5] so the answer is 4.

Example 2:

Input: arr = [2,4,6]
Output: 0
Explanation: All subarrays are [[2],[2,4],[2,4,6],[4],[4,6],[6]]
All sub-arrays sum are [2,6,12,4,10,6].
All sub-arrays have even sum and the answer is 0.

Example 3:

Input: arr = [1,2,3,4,5,6,7]
Output: 16

 

Constraints:

• 1 <= arr.length <= 105
• 1 <= arr[i] <= 100

Solutions

Solution 1

class Solution:
  def numOfSubarrays(self, arr: List[int]) -> int:
    mod = 10**9 + 7
    cnt = [1, 0]
    ans = s = 0
    for x in arr:
      s += x
      ans = (ans + cnt[s & 1 ^ 1]) % mod
      cnt[s & 1] += 1
    return ans

class Solution {
  public int numOfSubarrays(int[] arr) {
    final int mod = (int) 1e9 + 7;
    int[] cnt = {1, 0};
    int ans = 0, s = 0;
    for (int x : arr) {
      s += x;
      ans = (ans + cnt[s & 1 ^ 1]) % mod;
      ++cnt[s & 1];
    }
    return ans;
  }
}

class Solution {
public:
  int numOfSubarrays(vector<int>& arr) {
    const int mod = 1e9 + 7;
    int cnt[2] = {1, 0};
    int ans = 0, s = 0;
    for (int x : arr) {
      s += x;
      ans = (ans + cnt[s & 1 ^ 1]) % mod;
      ++cnt[s & 1];
    }
    return ans;
  }
};

func numOfSubarrays(arr []int) (ans int) {
  const mod int = 1e9 + 7
  cnt := [2]int{1, 0}
  s := 0
  for _, x := range arr {
    s += x
    ans = (ans + cnt[s&1^1]) % mod
    cnt[s&1]++
  }
  return
}

function numOfSubarrays(arr: number[]): number {
  let ans = 0;
  let s = 0;
  const cnt: number[] = [1, 0];
  const mod = 1e9 + 7;
  for (const x of arr) {
    s += x;
    ans = (ans + cnt[(s & 1) ^ 1]) % mod;
    cnt[s & 1]++;
  }
  return ans;
}