⚡Flashcard Drill➔
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

  1. Only the parity of each element matters, so reduce the array to a sequence of bits.
  2. A subarray has an odd sum exactly when its two bounding prefix parities differ.
  3. Track how many prefixes so far have even parity and how many have odd parity, seeded with one even prefix (the empty prefix).
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems