NeetCode #115LC-1524MediumArrays & Hashing
← Back to All Problems#115 · #1524 · Number of Sub-arrays With Odd Sum(和为奇数的子数组数目)
📌 Problem Statement & Constraints
Given an array of integers
arr, return the number of subarrays with an odd sum. The answer may be large, so return it modulo 10^9 + 7. Constraints: 1 <= arr.length <= 10^5, 1 <= arr[i] <= 100.💡 Core Algorithmic Approaches
- Only the parity of each element matters, so reduce the array to a sequence of bits.
- A subarray has an odd sum exactly when its two bounding prefix parities differ.
- Track how many prefixes so far have even parity and how many have odd parity, seeded with one even prefix (the empty prefix).
- For each new prefix, the number of new odd-sum subarrays ending here is the count of prefixes with the opposite parity.
💻 Benchmark Python3 Implementation
class Solution:
def numOfSubarrays(self, arr: List[int]) -> int:
MOD = 10 ** 9 + 7
even = 1 # empty prefix, parity 0
odd = 0
cur = 0
res = 0
for x in arr:
cur ^= (x & 1) # parity of the prefix
if cur:
res += even # pair with earlier even prefixes
odd += 1
else:
res += odd # pair with earlier odd prefixes
even += 1
return res % MOD⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass.
💾 Space Complexity
O(1): two counters.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the initial even prefix: subarrays starting at index 0 would be missed.
- Summing the raw values: only parities matter, and summing values would overflow for large inputs.
- Forgetting the modulo: the count can be up to ~5 * 10^9, which the problem requires reducing.
- Using the parity of the value rather than the prefix: the prefix parity is the XOR-accumulated parity, not the current element's.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.