Solution Explanation

This problem asks to find the number of subarrays with an odd sum within a given array. A naive approach would be to iterate through all possible subarrays, calculate their sums, and check if they're odd. However, this leads to O(n^2) time complexity, which is inefficient for large arrays.

The optimal solution leverages the concept of prefix sums and bit manipulation to achieve a linear time complexity, O(n).

Approach:

1. Prefix Sum and Parity: The key observation is that the sum of a subarray arr[i:j] can be expressed as the difference between two prefix sums: prefixSum[j] - prefixSum[i-1] (where prefixSum[k] is the sum of elements from arr[0] to arr[k]). Instead of directly tracking the sums, we only need to track the parity (even or odd) of the prefix sums. An odd subarray sum occurs when the parity of prefixSum[j] is different from the parity of prefixSum[i-1].

2. Counting Parity: We maintain a count of prefix sums with even and odd parity using an array cnt = [even_count, odd_count]. Initially, cnt = [1, 0] because the empty prefix (before the first element) has an even sum (0).

3. Iteration: We iterate through the array:

   • For each element x, update the prefix sum s += x.
   • Check the parity of s:
     • If s is even, it means we've added an odd number of odd elements to an even number of elements, or an even number of odd numbers to an even number of even numbers.
     • If s is odd, it means the total number of odd numbers added is odd.

4. Counting Odd Subarrays: The number of odd subarrays ending at the current position is the count of prefix sums with opposite parity. If s is even, we add cnt[1] (the count of odd prefix sums) to the total count of odd subarrays (ans). If s is odd, we add cnt[0] (the count of even prefix sums).

5. Modulo Operation: The problem specifies that the answer should be modulo 10^9 + 7 to handle potentially large results.

Time and Space Complexity Analysis:

• Time Complexity: O(n), as we iterate through the array once.
• Space Complexity: O(1), as we only use a constant amount of extra space (cnt array).

Code Explanation (Python):

class Solution:
    def numOfSubarrays(self, arr: List[int]) -> int:
        mod = 10**9 + 7
        cnt = [1, 0] # cnt[0]: even prefix sums, cnt[1]: odd prefix sums
        ans = s = 0
        for x in arr:
            s += x
            ans = (ans + cnt[s & 1 ^ 1]) % mod # Add count of opposite parity
            cnt[s & 1] += 1 # Increment count for current parity
        return ans
 

The s & 1 operation efficiently determines the parity of s (1 for odd, 0 for even). s & 1 ^ 1 flips the parity (0 becomes 1, 1 becomes 0). The modulo operation ensures the result stays within the allowed range. The code in other languages follows a similar logic and structure.