Skip to content

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

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)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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
    }
}

Comments