Skip to content

1524. Number of Sub-arrays With Odd Sum 👍

Approach 1: $O(n)$ space

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  int numOfSubarrays(vector<int>& arr) {
    constexpr int kMod = 1'000'000'007;
    const int n = arr.size();
    long ans = 0;
    // dp0[i] := the number of subarrays that end in arr[i - 1] with an even sum
    vector<int> dp0(n + 1);
    // dp1[i] := the number of subarrays that end in arr[i - 1] with an odd sum
    vector<int> 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;
  }
};

Approach 2: $O(1)$ space

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  int numOfSubarrays(vector<int>& arr) {
    constexpr int kMod = 1'000'000'007;
    long ans = 0;
    long dp0 = 0;
    long dp1 = 0;

    for (const int a : arr) {
      if (a % 2 == 1) {
        const int cache = dp0;
        dp0 = dp1;
        dp1 = cache + 1;
      } else {
        ++dp0;
      }
      ans = (ans + dp1) % kMod;
    }

    return ans;
  }
};