Sum of All Odd Length Subarrays

Problem Description

Given an array of positive integers arr, return the sum of all possible odd-length subarrays of arr. A subarray is a contiguous subsequence of the array.

Key Insights

• A subarray is defined as a contiguous part of the array.
• Odd-length subarrays can be of lengths 1, 3, 5, etc.
• Each element contributes to multiple odd-length subarrays depending on its position.
• We can calculate the contribution of each element to the total sum based on how many odd-length subarrays include that element.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve the problem, we need to determine how many odd-length subarrays each element belongs to. For an element at index i in an array of length n, we can derive its contribution using the following logic:

1. The total number of subarrays that can start from index i is (i + 1) * (n - i).
2. To find the number of odd-length subarrays, we need to consider the number of even and odd subarrays:
   • From the total subarrays, half (or nearly half) will be odd, depending on whether the total is even or odd.
3. Calculate the contribution of each element to the final sum by multiplying its value by the number of odd-length subarrays it belongs to.

Code Solutions