Code Implementation

class Solution:
    def numOfSubarrays(self, arr):
        MOD = 10**9 + 7
        odd = even = 0
        result = 0
        for num in arr:
            if num % 2 == 0:
                even += 1
            else:
                # swap odd and even, then increment odd
                odd, even = even, odd
                odd += 1
            result = (result + odd) % MOD
        return result
      

class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        int MOD = 1e9 + 7;
        int odd = 0, even = 0, result = 0;
        for (int num : arr) {
            if (num % 2 == 0) {
                even++;
            } else {
                int temp = odd;
                odd = even + 1;
                even = temp;
            }
            result = (result + odd) % MOD;
        }
        return result;
    }
};
      

class Solution {
    public int numOfSubarrays(int[] arr) {
        int MOD = 1000000007;
        int odd = 0, even = 0, result = 0;
        for (int num : arr) {
            if (num % 2 == 0) {
                even++;
            } else {
                int temp = odd;
                odd = even + 1;
                even = temp;
            }
            result = (result + odd) % MOD;
        }
        return result;
    }
}
      

var numOfSubarrays = function(arr) {
    const MOD = 1e9 + 7;
    let odd = 0, even = 0, result = 0;
    for (let num of arr) {
        if (num % 2 === 0) {
            even++;
        } else {
            let temp = odd;
            odd = even + 1;
            even = temp;
        }
        result = (result + odd) % MOD;
    }
    return result;
};
      

Problem Description

Thought Process

Solution Approach

• We maintain two counters: odd and even, where odd is the number of prefix sums with odd sum up to the current index, and even is the number of prefix sums with even sum up to the current index.
• Initially, the count of even prefix sums is 1 (the empty prefix), and the count of odd prefix sums is 0.
• As we iterate through each element:
  • If the current number is even, it does not change the parity of the prefix sum. So, the number of odd and even prefix sums remains the same, except we increment the number of even prefixes by 1 (for the new prefix ending at the current element).
  • If the current number is odd, it flips the parity of the prefix sum. So, the number of new odd prefixes becomes the previous even count (because even + odd = odd), and the number of new even prefixes becomes the previous odd count (because odd + odd = even). We also increment the count for the current element itself.
• At each step, the number of subarrays ending at the current index with an odd sum is equal to the current odd count.
• Sum up odd for each index to get the final answer.

Example Walkthrough

• Start: odd = 0, even = 0, result = 0
• First element (1):
  • 1 is odd, so swap odd/even: odd = 0, even = 0; then odd += 1 → odd = 1
  • result += odd → result = 1
• Second element (3):
  • 3 is odd, so swap odd/even: odd = 0, even = 1; then odd += 1 → odd = 2
  • result += odd → result = 3
• Third element (5):
  • 5 is odd, so swap odd/even: odd = 1, even = 2; then odd += 1 → odd = 3
  • result += odd → result = 6

Time and Space Complexity

• Brute-force approach: For every subarray, calculate the sum and check if it is odd. There are O(n²) subarrays, and each sum takes O(1) time if we use prefix sums, so total time is O(n²).
• Optimized approach (as above): We only need one pass through the array, updating counters in O(1) time per element. So, the total time complexity is O(n).
• Space complexity for both approaches is O(1) (not counting the input array), since we use only a few integer variables for counters.

Summary