Skip to content

1524. Number of Sub-arrays With Odd Sum

SourceBiweekly Contest 31 Q2DifficultyMediumRating1610

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

Thinking

Count subarrays whose sum is odd. There are \(O(n^2)\) of them and \(n\le 10^5\), so explicit sums fail. The parity of a subarray sum is the parity of the difference of two prefix sums.

An odd prefix pairs with every previous even prefix; an even prefix pairs with every previous odd one. While scanning we keep those two counters, add the matching count for the current prefix, then update. Reduce the answer modulo \(10^9+7\).

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