Leetcode 1524. Number of Sub-arrays With Odd Sum

Problem Description

The problem asks for the number of sub-arrays from a given array of integers that their sum is odd. It's important to note that the output may be large, so the result should be returned modulo 10^9 + 7.

Approach

To solve this problem, the solution applies the concept of dynamic programming. It keeps track of two arrays:

1. dp0[i], which denotes the number of sub-arrays that end with arr[i - 1] and have an even sum.
2. dp1[i], which denotes the number of sub-arrays that end with arr[i - 1] and have an odd sum.

Depending on whether the current element is even or odd, these arrays are updated accordingly.

Example

Consider arr = [1,2,3]. Initially, both dp0 and dp1 are empty. The outer loop runs over the array.

1. For i = 1, arr[i - 1] = 1 which is odd. So, dp0[i] = dp1[i - 1] = 0 and dp1[i] = dp0[i - 1] + 1 = 1. The total count of odd sums, ans, is incremented by dp1[i].
2. For i = 2, arr[i - 1] = 2 which is even. So, dp0[i] = dp0[i - 1] + 1 = 1 and dp1[i] = dp1[i - 1] = 1. The total count of odd sums remains unchanged.
3. For i = 3, arr[i - 1] = 3 which is odd. So, dp0[i] = dp1[i - 1] = 1 and dp1[i] = dp0[i - 1] + 1 = 2. The total count of odd sums, ans, is incremented by dp1[i].

Finally, ans is returned as the answer after taking modulo 10^9 + 7.

Python

1
2Python
3class Solution:
4    def numOfSubarrays(self, arr: List[int]) -> int:
5        mod = 10**9 + 7
6        n = len(arr)
7        dp0 = [0] * (n + 1)
8        dp1 = [0] * (n + 1)
9        ans = 0
10        
11        for i in range(1, n + 1):
12            if arr[i - 1] % 2 == 0:
13                dp0[i] = dp0[i - 1] + 1
14                dp1[i] = dp1[i - 1]
15            else:
16                dp0[i] = dp1[i - 1]
17                dp1[i] = dp0[i - 1] + 1
18            ans = (ans + dp1[i]) % mod
19        return ans

Java

1
2Java
3  public int numOfSubarrays(int[] arr) {
4    int mod = (int)1e9 + 7, n = arr.length;
5    int[] dp0 = new int[n + 1], dp1 = new int[n + 1];
6    int ans = 0;
7
8    for (int i = 1; i <= n; ++i) {
9      if (arr[i - 1] % 2 == 0) {
10          dp0[i] = dp0[i - 1] + 1;
11          dp1[i] = dp1[i - 1];
12      } else {
13          dp0[i] = dp1[i - 1];
14          dp1[i] = dp0[i - 1] + 1;
15      }
16      ans = (int)((ans + dp1[i]) % mod);
17    }
18    return ans;
19  }

JavaScript

1
2JavaScript
3var numOfSubarrays = function(arr) {
4    let mod = Math.pow(10, 9) + 7;
5    let n = arr.length;
6    let dp0 = new Array(n + 1).fill(0), dp1 = new Array(n + 1).fill(0);
7    let ans = 0;
8
9    for (let i = 1; i <= n; ++i) {
10        if (arr[i - 1] % 2 === 0) {
11            dp0[i] = dp0[i - 1] + 1;
12            dp1[i] = dp1[i - 1];
13        } else {
14            dp0[i] = dp1[i - 1];
15            dp1[i] = dp0[i - 1] + 1;
16        }
17        ans = (ans + dp1[i]) % mod;
18    }
19    return ans;
20};

C++

1
2C++
3class Solution {
4public:
5    int numOfSubarrays(vector<int>& arr) {
6        int mod = 1e9 + 7, n = arr.size();
7        vector<int> dp0(n + 1), dp1(n + 1);
8        long ans = 0;
9
10        for (int i = 1; i <= n; ++i) {
11            if (arr[i - 1] % 2 == 0) {
12                dp0[i] = dp0[i - 1] + 1;
13                dp1[i] = dp1[i - 1];
14            } else {
15                dp0[i] = dp1[i - 1];
16                dp1[i] = dp0[i - 1] + 1;
17            }
18            ans = (ans + dp1[i]) % mod;
19        }
20        return ans;
21    }
22};

C#

1
2C#
3public class Solution {
4public int NumOfSubarrays(int[] arr) {
5    int mod = (int)Math.Pow(10, 9) + 7;
6    int n = arr.Length;
7    int[] dp0 = new int[n + 1], dp1 = new int[n + 1];
8    int ans = 0;
9
10    for (int i = 1; i <= n; ++i) {
11        if (arr[i - 1] % 2 == 0) {
12            dp0[i] = dp0[i - 1] + 1;
13            dp1[i] = dp1[i - 1];
14        } else {
15            dp0[i] = dp1[i - 1];
16            dp1[i] = dp0[i - 1] + 1;
17        }
18        ans = (int)((ans + dp1[i]) % mod);
19    }
20    return ans;
21}
22}

In conclusion, this problem of counting the number of sub-arrays with odd sum can be solved by using dynamic programming principles. By keeping track of the number of sub-arrays ending with each element where the sum is odd or even, we can incrementally build the solution with each additional element. This approach minimizes redundant computation and leads to efficient solutions across multiple programming languages including Python, Java, JavaScript, C++, and C#.

However, it's not enough to just implement the right approach; one must also ensure its accuracy by testing across a range of inputs. Various edge-case scenarios such as an array with only even or only odd numbers, an empty array, or an array with negative numbers should be considered.

Remember, the ultimate goal in solving such problems is not just to arrive at the solution, but to understand the underlying principles and algorithms at play. In this case, gaining a solid understanding of dynamic programming - a widely utilized approach in computer programming - is the larger objective.