Problem Statement:

Given an array of positive integers arr, calculate the sum of all possible odd-length subarrays.

A subarray is a contiguous subsequence of the array.

Return the sum of all odd-length subarrays of arr.

Example:

Input: arr = [1,4,2,5,3]

Output: 58

Explanation: The odd-length subarrays of arr and their sums are:

[1] = 1

[4] = 4

[2] = 2

[5] = 5

[3] = 3

[1,4,2] = 7

[4,2,5] = 11

[2,5,3] = 10

[1,4,2,5,3] = 15

If we add all the sums together, we get 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

Solution:

The problem can be solved by following the given steps:

1. Initialize a variable 'sum' to 0.
2. Traverse the input array 'arr' using two nested loops. The outer loop will iterate over all possible subarrays of 'arr', and the inner loop will iterate over all elements within the subarray.
3. For each subarray, check if its length is odd.
4. If the length of the subarray is odd, calculate its sum and add it to the 'sum' variable.
5. Return the 'sum' variable as the final result.

Implementation:

Here is the Python implementation of the above approach:

def sumOddLengthSubarrays(arr): # Initialize the sum variable to 0 sum = 0 # Traverse the input array using two nested loops for i in range(len(arr)): for j in range(i, len(arr)): # Check if the length of the subarray is odd if (j - i + 1) % 2 == 1: # Calculate the sum of the current subarray for k in range(i, j+1): sum += arr[k] # Return the final sum return sum

Test the solution with the given example

arr = [1,4,2,5,3] print(sumOddLengthSubarrays(arr)) # Output: 58

Time and Space Complexity:

Time Complexity: The time complexity of the above algorithm is O(n^3), where 'n' is the length of the input array. This is because we are traversing the input array using two nested loops, and for each subarray, we are calculating its sum in an additional loop.

Space Complexity: The space complexity of the above algorithm is O(1), as we are not using any extra space to solve the problem, except for the 'sum' variable.

1