Given an array of integers arr. Return the number of sub-arrays with odd sum.

As the answer may grow large, the answer must be computed modulo 10^9 + 7.

Example 1:

Input: arr = [1,3,5]
Output: 4
Explanation: All sub-arrays are [,[1,3],[1,3,5],,[3,5],]
All sub-arrays sum are [1,4,9,3,8,5].
Odd sums are [1,9,3,5] so the answer is 4.


Example 2:

Input: arr = [2,4,6]
Output: 0
Explanation: All sub-arrays are [,[2,4],[2,4,6],,[4,6],]
All sub-arrays sum are [2,6,12,4,10,6].
All sub-arrays have even sum and the answer is 0.


Example 3:

Input: arr = [1,2,3,4,5,6,7]
Output: 16


Example 4:

Input: arr = [100,100,99,99]
Output: 4


Example 5:

Input: arr = 
Output: 1


Constraints:

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 100

## Solution: DP

We would like to know how many subarrays end with arr[i] have odd or even sums.

dp[i] := # end with arr[i] has even sum
dp[i] := # end with arr[i] has even sum

if arr[i] is even:

dp[i]=dp[i-1] + 1, dp[i]=dp[i-1]

else:

dp[i]=dp[i-1], dp[i]=dp[i-1] + 1

ans = sum(dp[i])

Time complexity: O(n)
Space complexity: O(n) -> O(1)

## Python3

If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website ## Be First to Comment

Mission News Theme by Compete Themes.