Sponsored
Sponsored
The brute force approach involves iterating over every possible subarray, checking if its length is odd, and then summing its elements. This approach is straightforward but not optimal.
Time Complexity: O(n^3) where n is the number of elements in the array, due to triple nested loops.
Space Complexity: O(1), only a few extra variables are utilized.
1def sumOddLengthSubarrays(arr):
2 total_sum = 0
3 n = len(arr)
4 for start in range(n):
5 for end in range(start, n):
6 if (end - start + 1) % 2 != 0:
7 total_sum += sum(arr[start:end+1])
8 return total_sum
9
10arr = [1, 4, 2, 5, 3]
11print(sumOddLengthSubarrays(arr))Python offers an elegant solution by using list comprehension and built-in sum function. The code iterates over all possible subarrays and calculates their sums if the length is odd.
The optimized approach calculates the contribution of each element to the final sum using a mathematical formula. For each element at index i, calculate how many odd-length subarrays it can contribute to, then sum directly based on these contributions.
Time Complexity: O(n), much improved by calculating contributions directly.
Space Complexity: O(1), only a few extra integer variables.
1
This solution computes the contribution of each element to possible odd-length subarrays using a mathematical formula. For each element, calculate how many subarrays include the element, split this into odd/even counts, and then use that to determine its overall contribution to the sum.