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
Solution
Python3
class Solution:
def numOfSubarrays(self, arr: List[int]) -> int:
M = 10 ** 9 + 7
res = even = odd = 0
for x in arr:
if x % 2 == 1:
odd, even = even + 1, odd
else:
even += 1
res += odd
res %= M
return res
C++
class Solution {
public:
int numOfSubarrays(vector<int>& A) {
int cur = 0, odd = 0, even = 1, mod = (int)1e9 + 7, res = 0;
for (int a: A) {
cur += a;
if (cur%2){
res = (res+even)%mod;
odd++;
}else{
res = (res+odd)%mod;
even++;
}
}
return res;
}
};