Problem 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 10^9 + 7.
Key Insights
- A subarray is defined as a contiguous part of an array.
- The sum of a subarray can be classified as either odd or even.
- The sum of an odd-length subarray is odd if it starts with an odd number and contains an even number of even numbers.
- The sum of an even-length subarray is odd if it starts with an even number and contains an odd number of odd numbers.
- We can use a prefix sum approach to efficiently count the number of subarrays with odd sums.
Space and Time Complexity
Time Complexity: O(n)
Space Complexity: O(1)
Solution
To solve the problem, we can maintain a count of the prefix sums that are odd and even as we iterate through the array. We initialize both counts to zero and increment them based on whether the current prefix sum is odd or even. For each element in the array, we update the prefix sum and check its parity. Depending on the parity of the prefix sum, we can determine how many valid subarrays with odd sums can be formed using the counts we've maintained.