1524. Number of Sub-arrays With Odd Sum

Problem Link

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:
 
        odd = even = res = 0
        M = 1000000007
        
        for num in arr:
            if num & 1:
                odd, even = even+1, odd
            else:
                odd, even = odd, even+1
                
            res += odd
        
        return res%M
        

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;
    }
        
};