# Number of Sub-arrays With Odd Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-sub-arrays-with-odd-sum)
Canonical: https://scaleengineer.com/dsa/problems/number-of-sub-arrays-with-odd-sum
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
**Companies:** [Directi](https://scaleengineer.com/companies/directi)
---
## Problem
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`

# Approaches
## Brute Force Enumeration
This is the most straightforward but also the most inefficient approach. It involves generating every possible subarray, calculating the sum of its elements, and checking if the sum is odd. A counter is maintained for subarrays that satisfy the condition.
**Time:** O(N³), where N is the number of elements in `arr`. The three nested loops lead to a cubic time complexity, which is very slow. · **Space:** O(1), as we only use a few variables to store indices and the current sum. No extra space proportional to the input size is needed.
**Pros:** Very simple to understand and implement.; Requires no special data structures or complex logic.
**Cons:** Extremely inefficient due to three nested loops.; Will result in a 'Time Limit Exceeded' error for the given constraints.
### Explanation
The brute-force method systematically checks every single contiguous subarray within the given array `arr`. It uses three nested loops to achieve this:

- The first loop, with index `i`, iterates from the beginning to the end of the array to select the starting element of a subarray.
- The second loop, with index `j`, iterates from `i` to the end of the array to select the ending element of the subarray.
- The third loop, with index `k`, iterates from `i` to `j` to compute the sum of the elements in the current subarray `arr[i...j]`.

After calculating the sum, we check if it's odd. If it is, we increment a counter. To handle potentially large results, the counter is updated using modulo arithmetic at each increment. While simple to understand, its cubic time complexity makes it impractical for large inputs.

```java
class Solution {
    public int numOfSubarrays(int[] arr) {
        int n = arr.length;
        int result = 0;
        int MOD = 1_000_000_007;

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int currentSum = 0;
                for (int k = i; k <= j; k++) {
                    currentSum += arr[k];
                }
                if (currentSum % 2 != 0) {
                    result = (result + 1) % MOD;
                }
            }
        }
        return result;
    }
}
```
### Algorithm
1. Initialize `result = 0` and `MOD = 1_000_000_007`.
2. Use a nested loop to define the start (`i`) and end (`j`) of each subarray.
3. For each subarray `arr[i...j]`, use a third loop to iterate from `i` to `j` and calculate its sum.
4. Check if the sum is odd (`sum % 2 != 0`).
5. If the sum is odd, increment the `result` counter, applying the modulo operation: `result = (result + 1) % MOD`.
6. After checking all subarrays, return `result`.

## Optimized Brute Force with Cumulative Sum
This approach is an optimization of the pure brute-force method. Instead of recalculating the sum of each subarray from scratch, we use a running sum. We iterate through all possible starting points and, for each, extend the subarray one element at a time, updating the sum and checking its parity.
**Time:** O(N²), where N is the length of the array. The two nested loops result in quadratic time complexity. · **Space:** O(1), as we only use a constant amount of extra space for variables.
**Pros:** Significantly faster than the O(N³) approach.; Remains relatively simple to implement.
**Cons:** Still inefficient for large inputs.; Guaranteed to time out on competitive programming platforms for constraints like N = 10^5.
### Explanation
We can eliminate one of the nested loops from the previous approach. We still use two nested loops to define all subarrays.

- The outer loop (with index `i`) fixes the starting point of the subarray.
- The inner loop (with index `j`) iterates from `i` to the end of the array. This loop defines the ending point and effectively extends the subarray one element at a time.

A variable `currentSum` is maintained for each starting point `i`. As the inner loop progresses, `currentSum` is updated by adding the next element `arr[j]`. This `currentSum` represents the sum of the subarray `arr[i...j]`. After each update, we check if `currentSum` is odd and update our result counter accordingly. This reduces the complexity from cubic to quadratic.

```java
class Solution {
    public int numOfSubarrays(int[] arr) {
        int n = arr.length;
        int result = 0;
        int MOD = 1_000_000_007;

        for (int i = 0; i < n; i++) {
            int currentSum = 0;
            for (int j = i; j < n; j++) {
                currentSum += arr[j];
                if (currentSum % 2 != 0) {
                    result = (result + 1) % MOD;
                }
            }
        }
        return result;
    }
}
```
### Algorithm
1. Initialize `result = 0` and `MOD = 1_000_000_007`.
2. Use an outer loop with index `i` to fix the starting point of subarrays.
3. Inside, initialize `currentSum = 0`.
4. Use an inner loop with index `j` starting from `i` to extend the subarray to the right.
5. In the inner loop, update the sum: `currentSum += arr[j]`.
6. Check if `currentSum` is odd. If so, increment `result` with modulo: `result = (result + 1) % MOD`.
7. After the loops complete, return `result`.

## Prefix Sum Parity Counting
This is the most efficient approach, solving the problem in a single pass. It relies on the mathematical property of sums and parity. The sum of a subarray `arr[i...j]` is odd if and only if the parity of the prefix sum up to `j` is different from the parity of the prefix sum up to `i-1`. By keeping track of the counts of even and odd prefix sums seen so far, we can calculate the result in linear time.
**Time:** O(N), where N is the length of the array. We iterate through the array only once. · **Space:** O(1), as it only requires a few variables to store the counts and current parity, regardless of the input size.
**Pros:** Optimal time complexity, making it very fast.; Optimal space complexity.; Passes for all constraints.
**Cons:** The logic is less direct and might require some thought to understand compared to brute-force methods.
### Explanation
The key insight is that `sum(arr[i..j]) = prefixSum[j] - prefixSum[i-1]`. For this sum to be odd, the parities must differ:
- `odd_sum = odd_prefix - even_prefix`
- `odd_sum = even_prefix - odd_prefix`

We can iterate through the array once, maintaining a running sum's parity. We also keep two counters: `oddCount` for the number of prefix sums with odd parity encountered so far, and `evenCount` for those with even parity. We initialize `evenCount = 1` to account for the empty prefix sum (sum=0, which is even).

For each element `arr[i]`, we update the current prefix sum's parity. 
- If the new prefix sum is odd, it can be paired with any of the `evenCount` previously seen even prefix sums to form a subarray with an odd sum. We add `evenCount` to our result and then increment `oddCount`.
- If the new prefix sum is even, it can be paired with any of the `oddCount` previously seen odd prefix sums. We add `oddCount` to our result and then increment `evenCount`.

This method avoids nested loops entirely, leading to an optimal solution.

```java
class Solution {
    public int numOfSubarrays(int[] arr) {
        int MOD = 1_000_000_007;
        int oddCount = 0;  // count of prefix sums with odd parity
        int evenCount = 1; // count of prefix sums with even parity (starts with 1 for empty prefix sum 0)
        int result = 0;
        int currentSumParity = 0; // 0 for even, 1 for odd

        for (int num : arr) {
            currentSumParity = (currentSumParity + num) % 2;
            if (currentSumParity == 1) { // current prefix sum is odd
                // Pair with previous even prefix sums
                result = (result + evenCount) % MOD;
                oddCount++;
            } else { // current prefix sum is even
                // Pair with previous odd prefix sums
                result = (result + oddCount) % MOD;
                evenCount++;
            }
        }
        return result;
    }
}
```
### Algorithm
1. Initialize `odd = 0` (count of odd-parity prefix sums), `even = 1` (for the initial even-parity prefix sum of 0), `result = 0`, and `currentParity = 0`.
2. Define `MOD = 1_000_000_007`.
3. Iterate through each number `num` in `arr`.
4. Update the parity of the running sum: `currentParity = (currentParity + num) % 2`.
5. If `currentParity` is 1 (odd):
   - The number of new odd-sum subarrays ending here is `even`.
   - Update `result = (result + even) % MOD`.
   - Increment `odd`.
6. If `currentParity` is 0 (even):
   - The number of new odd-sum subarrays ending here is `odd`.
   - Update `result = (result + odd) % MOD`.
   - Increment `even`.
7. Return `result`.

# Solutions
### Java

```java
class Solution {
public
  int numOfSubarrays(int[] arr) {
    final int mod = (int)1 e9 + 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;
  }
}

```

### CPP

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

### Python

```python
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

```