Medium

Number of Sub-arrays With Odd Sum

LAB

Return the number of contiguous subarrays with odd sum, modulo 1000000007.

EXAMPLES

Example 1

Input
{
  "arr": [
    1,
    3,
    5
  ]
}

Output
4

FUNCTION SHAPE

arr: intArray→int

SOLUTION NOTE

This is the exact same idea as before. If the current prefix sum is odd, a previous even prefix sum carves out an odd subarray sum. If the current prefix sum is even, a previous odd prefix sum carves out an odd subarray sum.

Reveal reference solution +

pythonREFERENCE

def numOfSubarrays(self, arr: List[int]) -> int:
    even_odd_prefix_sum, prefix_sum, res = [1, 0], 0, 0

    for a in arr:
        prefix_sum += a
        even_odd_prefix_sum[prefix_sum % 2] += 1
        res = (res + even_odd_prefix_sum[not (prefix_sum % 2)]) % (10**9+7)

    return res

TimeO(n)

SpaceO(1)

Open on LeetCode ↗