algoadvance

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:

Example 1:

• Input: arr = [1,4,2,5,3]
• Output: 58
• Explanation: The odd-length subarrays of [1,4,2,5,3] and their sums are:
  • [1] -> 1
  • [4] -> 4
  • [2] -> 2
  • [5] -> 5
  • [3] -> 3
  • [1,4,2] -> 1 + 4 + 2 = 7
  • [4,2,5] -> 4 + 2 + 5 = 11
  • [2,5,3] -> 2 + 5 + 3 = 10
  • [1,4,2,5,3] -> 1 + 4 + 2 + 5 + 3 = 15
  • If you add up all of these sums, you get 58.

Example 2:

• Input: arr = [1,2]
• Output: 3
• Explanation: There are only 2 subarrays of odd length: [1] and [2]. Their sum is 1 + 2 = 3.

Example 3:

• Input: arr = [10,11,12]
• Output: 66

Constraints:

• 1 <= arr.length <= 100
• 1 <= arr[i] <= 1000

Clarifying Questions

1. Should we consider subarrays of length 1? (Yes, because they are of odd length)
2. Is the sum guaranteed to fit within standard integer range in Python? (Yes, Python integers can handle large sums).

Strategy

1. Iterate over all possible starting indices of the subarray.
2. For each starting index, create subarrays of increasing odd lengths.
3. Calculate the sum of each odd-length subarray and add it to a running total.

Code

def sumOddLengthSubarrays(arr):
    total_sum = 0
    n = len(arr)
    
    for i in range(n):
        current_sum = 0
        for j in range(i, n):
            current_sum += arr[j]
            if (j - i) % 2 == 0:  # Check for odd length
                total_sum += current_sum

    return total_sum

# Test Cases
print(sumOddLengthSubarrays([1,4,2,5,3]))  # Expected output: 58
print(sumOddLengthSubarrays([1,2]))        # Expected output: 3
print(sumOddLengthSubarrays([10,11,12]))   # Expected output: 66

Time Complexity

• The time complexity is O(n^2) due to the nested loops iterating over the array to form subarrays.
• The space complexity is O(1) since only a few extra variables are used regardless of the input size.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?