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.
1#include <stdio.h>
2
3int sumOddLengthSubarrays(int *arr, int arrSize) {
4 int totalSum = 0;
5 for (int start = 0; start < arrSize; start++) {
6 for (int end = start; end < arrSize; end++) {
7 if ((end - start + 1) % 2 != 0) {
8 for (int k = start; k <= end; k++) {
9 totalSum += arr[k];
10 }
11 }
12 }
13 }
14 return totalSum;
15}
16
17int main() {
18 int array[] = {1, 4, 2, 5, 3};
19 int result = sumOddLengthSubarrays(array, 5);
20 printf("%d\n", result);
21 return 0;
22}This C program utilizes nested loops to generate subarrays. The outer two loops iterate through all start and end indices. The innermost loop sums the elements of the current subarray if its 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#include <vector>
using namespace std;
int sumOddLengthSubarrays(vector<int>& arr) {
int totalSum = 0, n = arr.size();
for (int i = 0; i < n; i++) {
int leftCount = i + 1;
int rightCount = n - i;
int oddCount = (leftCount * rightCount + 1) / 2;
totalSum += oddCount * arr[i];
}
return totalSum;
}
int main() {
vector<int> arr = {1, 4, 2, 5, 3};
cout << sumOddLengthSubarrays(arr) << endl;
return 0;
}This C++ implementation calculates contributions of each array element towards the final result by counting involving subarrays through simplified arithmetic operations.