Problem Breakdown
We are given an array of integers arr. The goal is to count how many contiguous sub-arrays have a sum that is odd. We must return the result modulo .
Inputs: An integer list arr where length ranges from 1 to and values are between 1 and 100 (though parity logic holds regardless of value range).
Outputs: A single non-negative integer representing the count.
Implicit Constraints & Edge Cases:
- Modulo Arithmetic: The result can exceed standard integer limits in languages like C++/Java, so we must apply modulo . Python handles large integers automatically, but applying the modulus at return is required by problem spec.
- Sub-array Definition: Any slice
arr[i:j]inclusive of start and exclusive of end (standard definition). - Initial State: The sum before any elements are processed is effectively 0 (even), which acts as a virtual prefix for sub-arrays starting at index 0.
Intuition
A naive approach would iterate through every possible pair (i, j) representing start and end indices of a sub-array, calculate the sum using slicing or accumulation, check parity, and increment a counter.
- Brute Force Complexity: because there are roughly sub-arrays. Given , this will Time Out (TLE).
Key Insight: Prefix Sums & Parity Properties.
The sum of a sub-array arr[i..j] can be expressed as the difference between two prefix sums: Prefix[j+1] - Prefix[i-1].
In modular arithmetic modulo 2 (parity):
(Odd + Even) % 2 = Odd(Even + Even) % 2 = Even(Odd + Odd) % 2 = Even
Essentially, a sub-array sum is odd if and only if the two prefix sums defining it have different parities. One must be even and one odd. If we know how many times an “even” prefix sum has occurred previously in our scan, and we encounter an “odd” current prefix sum now, every previous occurrence of that specific parity forms a valid sub-array with us right here.
Approach
- Initialize
total_odd_subarrays = 0. - Maintain counters for how many times we have seen:
- An even running prefix sum so far (
count_even). - An odd running prefix sum so far (
count_odd).
- An even running prefix sum so far (
- Start with a virtual prefix sum of
0(which is even). So, initializecount_even = 1,count_odd = 0. - Iterate through each number in the array:
- Update the current running sum parity by adding the current element modulo 2.
- If the new prefix sum is odd: It can form an odd sub-array with any previous even prefix sums found so far. Add
count_evento our total answer, then incrementcount_odd. - If the new prefix sum is even: It can form an odd sub-array with any previous odd prefix sums found so far. Add
count_oddto our total answer, then incrementcount_even.
- Return the accumulated count modulo .
Complexity Analysis
- Time Complexity: where is the length of
arr. We iterate through the array exactly once performing constant-time operations per element. - Space Complexity: . We only store a few integer counters regardless of input size (excluding Python’s internal large int storage overhead).
Solution
class Solution:
def numOfSubarrays(self, arr: List[int]) -> int:
MOD = 10**9 + 7
# Counters for prefix sums parity.
# Initial sum is 0 (even), so we start with one even count.
odd_count = 0
even_count = 1
current_sum_parity = 0
total_odd_subarrays = 0
for num in arr:
# Update running parity based on the number's parity
# (num % 2) is sufficient to track sum parity without full value.
if num % 2 == 1:
current_sum_parity ^= 1
# If current prefix is odd, it pairs with all previous even prefixes
if current_sum_parity == 1:
total_odd_subarrays = (total_odd_subarrays + even_count) % MOD
odd_count += 1
else:
# If current prefix is even, it pairs with all previous odd prefixes
total_odd_subarrays = (total_odd_subarrays + odd_count) % MOD
even_count += 1
return total_odd_subarrays
Edge Cases Handled
- Single Element Array: The loop runs once. If the element is odd,
even_count(initially 1) pairs with it to make a sub-array sum of that single element. Correct. - All Even Numbers:
current_sum_parityremains even throughout. We only addodd_countwhich stays at 0. Result is 0. Correct. - Large Output Count: The modulo operation ensures the result fits within standard integer limits for languages like Java/C++, and adheres to problem requirements in Python as well.