1524. Number of Sub-arrays With Odd Sum

Time: O(n)

Space: O(n)

Intuition

Count subarrays with odd sum. Track parity of prefix sums. When prefix is odd, pair with previous even prefix sums; when even, pair with odd.

Algorithm

1even_count=1, odd_count=0. running_sum=0.
2For each element: running_sum += element. If odd: result += even_count, odd_count++. Else: result += odd_count, even_count++.

Common Pitfalls

•Start with even_count=1 for the empty prefix. Odd+even or even+odd sums create odd result.

1524.cs

// Approach: DP tracking count of even-sum subarrays ending here; an odd current element swaps even/odd counts.
// Time: O(n) Space: O(n)

public class Solution
{
    public int NumOfSubarrays(int[] arr)
    {
        const int kMod = 1_000_000_007;
        int n = arr.Length;
        long ans = 0;

        // dp0[i] := the number of subarrays that end in arr[i - 1] with an even sum
        int[] dp0 = new int[n + 1];
        // dp1[i] := the number of subarrays that end in arr[i - 1] with an odd sum
        int[] dp1 = new int[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 (int)ans;
    }
}

Was this solution helpful?