Segments With an Odd Sum

Medium

You are given an array of positive integers values. Count the non-empty segments (contiguous pieces of the array) whose element sum is odd. Segments with different bounds count separately, even when their contents match. The answer may be large, so return it modulo 10⁹ + 7.

Example 1

values=[2, 3, 4] → 4

The segments are [2]=2, [2, 3]=5, [2, 3, 4]=9, [3]=3, [3, 4]=7, [4]=4. Four of them have an odd sum.

Example 2

values=[8, 6] → 0

Every number is even, so every sum is even.

Example 3

values=[1, 1, 1, 1] → 6

Constraints

1 ≤ len(values) ≤ 10⁵
1 ≤ values[i] ≤ 100

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Math Dynamic Programming Prefix Sum

Similar problems

The Growing Grab Limit Medium Merge the Front Tiles Hard Total Strength of All Squads Hard Split Into a Climb and a Descent Hard Split Into a Climb and a Descent: Large Values Hard

Input

values=[2, 3, 4]

Expected

Run checks the first 3 tests in your browser. Submit checks all 73 tests on the server, hidden ones included.