Number of Sub-arrays With Odd Sum Solution in C++

Explore Solutions in Other Languages


class Solution {
 public:
  int numOfSubarrays(vector& arr) {
    constexpr int kMod = 1'000'000'007;
    const int n = arr.size();
    long ans = 0;
    vector dp0(n + 1);
    vector dp1(n + 1);

    for (int i = 1; i <= n; ++i) {
      if (arr[i - 1] % 2 == 1) {
        dp0[i] = dp1[i - 1];
        dp1[i] = dp0[i - 1] + 1;
      } else {
        dp0[i] = dp0[i - 1] + 1;
        dp1[i] = dp1[i - 1];
      }
      ans = (ans + dp1[i]) % kMod;
    }

    return ans;
  }
};

Problem Description

The "Number of Sub-arrays With Odd Sum" problem involves counting how many contiguous subarrays of a given array have an odd sum.
Imagine you’re at a party, counting how many people are wearing odd-numbered shirts. It seems simple, but what if the shirts keep changing colors?
This problem is about finding those elusive odd sums in a sea of numbers.

Approach

The approach used in the code is dynamic programming. We maintain two arrays, dp0 and dp1, where dp0[i] counts the number of subarrays ending at index i-1 with an even sum, and dp1[i] counts those with an odd sum.
As we iterate through the array, we update these counts based on whether the current element is odd or even. The final answer is the sum of all odd subarrays, modulo \(10^9 + 7\).

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n) - We traverse the array once.
Space Complexity	O(n) - We use two additional arrays of size n + 1.

Real-World Example

Imagine you’re at a buffet, counting how many plates of food you’ve taken that have an odd number of items. Each time you take a plate, you either add an odd or even number of items.
The challenge is to keep track of how many plates you’ve taken that have an odd total. This is exactly what the problem is asking you to do with subarrays!