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

Solution

number-of-sub-arrays-with-odd-sum.py

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

number-of-sub-arrays-with-odd-sum.cpp

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

};