Thursday, July 22, 2021

Sum of All Odd Length Subarrays

Problem:

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

Example,
arr = [1, 4, 2, 5, 3]

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 these together we get 1+4+2+5+3+7+11 = 58

Approach:
From Subarray Sums the occurrences we can divide by 2 and can take it to calculate the odd length subarray sum.

Simply by traversing the whole array we can do,

occurences = ((i + 1) * (n - i))
result += (arr[i] * (  (occurences + 1)/ 2 ) ) // taking ceil

No comments:

Post a Comment