README_EN.md

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

Python3

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        MOD = int(1e9) + 7
        counter = [0] * 2
        s = ans = 0
        for v in arr:
            s += v
            counter[s % 2] += 1
            if s % 2 == 1:
                ans += 1 + counter[0]
            else:
                ans += counter[1]
        return ans % MOD

Java

class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int numOfSubarrays(int[] arr) {
        int[] counter = new int[2];
        int s = 0, ans = 0;
        for (int v : arr) {
            s += v;
            ++counter[s % 2];
            if (s % 2 == 1) {
                ans = (ans + 1 + counter[0]) % MOD;
            } else {
                ans = (ans + counter[1]) % MOD;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        const int MOD = 1e9 + 7;
        vector<int> counter(2);
        int s = 0, ans = 0;
        for (int& v : arr)
        {
            s += v;
            ++counter[s % 2];
            if (s % 2 == 1) ans = (ans + 1 + counter[0]) % MOD;
            else ans = (ans + counter[1]) % MOD;
        }
        return ans;
    }
};

Go

func numOfSubarrays(arr []int) int {
	const MOD = 1e9 + 7
	counter := make([]int, 2)
	s, ans := 0, 0
	for _, v := range arr {
		s += v
		counter[s%2]++
		if s%2 == 1 {
			ans = (ans + 1 + counter[0]) % MOD
		} else {
			ans = (ans + counter[1]) % MOD
		}
	}
	return ans
}

...