LeetCode 1524. Number of Sub-arrays With Odd Sum Solution in Java, C++, Python & More | Explanation + Code

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 cnt of length 2 as a counter, where cnt[0] and cnt[1] represent the number of subarrays with even and odd prefix sums, respectively. Initially, cnt[0] = 1 and cnt[1] = 0.

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

Traverse the array arr, for each element x encountered, add the value of x to s, then based on the parity of s, add the value of cnt[s \mod 2 \oplus 1] to the answer, and then increment the value of 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 arr. Space complexity is O(1).

PythonJavaC++GoTypeScriptRust

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)

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 } }(code-box)