All problems

Half-Total Stretches

Medium · prefix sum

Sana runs a market stall. At the end of every week she writes down her profit, which can be negative if the week went badly. The list profits holds these numbers in order.

A stretch is one or more weeks in a row. Its value is the sum of the profits of those weeks.

Sana wonders how often a stretch is worth exactly half of the profit of the whole list. Return the number of such stretches. Stretches that start or end in different weeks are counted separately, even if their numbers look the same.

If the profit of the whole list is odd, its half is not a whole number, so no stretch can match and the answer is 0. If the whole profit is 0, its half is 0.

Examples

Example 1

Input: profits = [2, -1, 3, 0]

Output: 3

The whole list adds up to 4, so we want stretches worth 2. They are [2], [-1, 3] and [-1, 3, 0].

Example 2

Input: profits = [1, 2]

Output: 0

The whole list adds up to 3, which is odd.

Example 3

Input: profits = [0, 0]

Output: 3

The whole list adds up to 0, so we want stretches worth 0: each single week and both weeks together.

Constraints