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 10⁹ + 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 <= 10⁵
1 <= arr[i] <= 100

Solutions

Solution 1: Prefix Sum + Counter

We define an array $\textit{cnt}$ of length 2 as a counter, where $\textit{cnt}[0]$ and $\textit{cnt}[1]$ represent the number of subarrays with even and odd prefix sums, respectively. Initially, $\textit{cnt}[0] = 1$ and $\textit{cnt}[1] = 0$.

Next, we maintain the current prefix sum $s$, initially $s = 0$.

Traverse the array $\textit{arr}$, for each element $x$ encountered, add the value of $x$ to $s$, then based on the parity of $s$, add the value of $\textit{cnt}[s \mod 2 \oplus 1]$ to the answer, and then increment the value of $\textit{cnt}[s \mod 2]$ by 1.

After the traversal, we get the answer. Note the modulo operation for the answer.

Time complexity is $O(n)$, where $n$ is the length of the array $\textit{arr}$. Space complexity is $O(1)$.

Python3

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

Java

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

C++

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

Go

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
}

TypeScript

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

Rust

impl Solution {
    pub fn num_of_subarrays(arr: Vec<i32>) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let mut cnt = [1, 0];
        let mut ans = 0;
        let mut s = 0;
        for &x in arr.iter() {
            s += x;
            ans = (ans + cnt[((s & 1) ^ 1) as usize]) % MOD;
            cnt[(s & 1) as usize] += 1;
        }
        ans
    }
}