Given an array of optimistic integers arr, return the sum of all potential odd-length subarrays of arr.

A subarray is a contiguous subsequence of the array.

Comply with up:

May you remedy this downside in O(n) time complexity?

Beneath are the three approaches from brute pressure technique to Greatest Case Runtime.



1. O(N^2 * log n)

var sumOddLengthSubarrays = perform(arr) {
    let consequence = 0;
    for(let i = 0; i < arr.size; i++){
        consequence += 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++){
                consequence += arr[t];
            }
        }
    }

    return consequence;
};

Enter fullscreen modeExit fullscreen mode



2. O(N^2)

var sumOddLengthSubarrays = perform(arr) {
    let consequence = 0;
    let lastWindowSum = 0;
    for(let i = 0; i < arr.size; i++){
        consequence += 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.
            consequence += 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 consequence;
};
Enter fullscreen modeExit fullscreen mode



3. O(N)

To unravel this downside in O(N) time we’ve got to calculate what number of sub arrays from an index could 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 are able to multiply this index witht the variety of sub arrays to get last results of present index’ sum.

To test what number of occasions a quantity can seem in a subarray or that what number of subarrays could be created with this present quantity we apply this under formulla.

whole occurrances = (currentIndex + 1) * (arrayLength - currentIndex) + 1);
Enter fullscreen modeExit fullscreen mode
occurrances in solely odd array = (currentIndex + 1) * (arrayLength - currentIndex) + 1) / 2
Enter fullscreen modeExit fullscreen mode

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.
Enter fullscreen modeExit fullscreen mode

For JavaScript we’ve got to parseInt – parseInt(((i + 1) * (arr.size - i) + 1) / 2) * arr[i]

var sumOddLengthSubarrays = perform(arr) {
    let consequence = 0;

    for(let i = 0; i < arr.size; ++i) {
        consequence += parseInt(((i + 1) * (arr.size - i) + 1) / 2) * arr[i];
    }

    return consequence;
};
Enter fullscreen modeExit fullscreen mode

 

Thanks for studying. 🙋‍



Abu Sayed is the Best Web, Game, XR, Blockchain Developer, Producer and Singer in Bangladesh. Don't forget to Checkout his Latest Songs.


Read More