Given an array of constructive integers arr, return the sum of all doable odd-length subarrays of arr.
A subarray is a contiguous subsequence of the array.
Observe up:
Might you resolve this downside in O(n) time complexity?
Beneath are the three approaches from brute pressure methodology to Greatest Case Runtime.
1. O(N^2 * log n)
var sumOddLengthSubarrays = operate(arr) {
let end result = 0;
for(let i = 0; i < arr.size; i++){
end result += arr[i]
}
for(let i = 0; i < arr.size; i++){
for(let j = i + 2; j < arr.size; j += 2){
for(let t = i; t <= j; t++){
end result += arr[t];
}
}
}
return end result;
};
2. O(N^2)
var sumOddLengthSubarrays = operate(arr) {
let end result = 0;
let lastWindowSum = 0;
for(let i = 0; i < arr.size; i++){
end result += arr[i]
}
for(let i = 0; i < arr.size; i++){
for(let j = i + 2; j < arr.size; j += 2){
// if that is the primary time then add present begin index to window sum.
if(lastWindowSum === 0) lastWindowSum = arr[i];
// memoized sum + subsequent newly added components solely.
end result += lastWindowSum + arr[j] + arr[j - 1];
// memoize the earlier window sum
lastWindowSum += arr[j] + arr[j - 1];
}
// reset final window when new window begins [the position of subarray starts change]
lastWindowSum = 0;
}
return end result;
};
3. O(N)
To unravel this downside in O(N) time we’ve got to calculate what number of sub arrays from an index may be made, after that we devide it by 2 and get the odd sub arrays.
As soon as we’ve got the variety of odd sub arrays for an Index we will multiply this index witht the variety of sub arrays to get remaining results of present index’ sum.
To test what number of instances a quantity can seem in a subarray or that what number of subarrays may be created with this present quantity we apply this under formulla.
complete occurrances = (currentIndex + 1) * (arrayLength - currentIndex) + 1);
occurrances in solely odd array = (currentIndex + 1) * (arrayLength - currentIndex) + 1) / 2
And to get the sum from the odd arrays we multiply the occurrance with present quantity.
sum in odd array = (currentIndex + 1) * (arrayLength - currentIndex) + 1) / 2 * currentNumber.
For JavaScript we’ve got to parseInt –
parseInt(((i + 1) * (arr.size - i) + 1) / 2) * arr[i]
var sumOddLengthSubarrays = operate(arr) {
let end result = 0;
for(let i = 0; i < arr.size; ++i) {
end result += parseInt(((i + 1) * (arr.size - i) + 1) / 2) * arr[i];
}
return end result;
};
Thanks for studying. 🙋
