45. Odd Stretch Totals
A shop records its daily takings in nums. A stretch is any run of consecutive days. For every stretch whose length is odd (1, 3, 5, ...), add up the takings on its days, then add all of those stretch totals together.
Return that grand total. Each distinct stretch is counted once, even when two stretches contain the same numbers.
Listing every stretch works but is slow. Instead, count how many odd-length stretches cover each position and multiply by the value there; that gives a linear-time solution. The answer always fits in a 32-bit signed integer.
Example 1
- Input:
- nums = [2,6,4]
- Output:
- 24
- Explanation:
The odd-length stretches are [2], [6], [4] and [2, 6, 4], with totals 2, 6, 4 and 12, so the answer is 24.
Example 2
- Input:
- nums = [10,11]
- Output:
- 21
- Explanation:
Only the two single-day stretches exist, so the total is 21.
Constraints
1 ≤ nums.length ≤ 100
1 ≤ nums[i] ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)