Program to Find Sum of All Odd Length Subarrays.

Given a positive integer array num of size n, calculate and return the sum of all possible odd-length subarrays of num.

Example:

Example 1:
Input: num[] = {1, 3, 2, 5, 6};
Output: 63


Explanation: 
List of Odd length subarrays:

[1] = 1

[3] = 3

[2] = 2

[5] = 5

[6] = 6

[1, 3, 2] = 6

[3, 2, 5] = 10

[2, 5, 6] = 13

[1, 3, 2, 5, 6] = 17

Sum of all odd length arrays: 1+3+2+5+6+6+10+13+17 = 63


Example 2:
Input: num[] = {3, 5}
Output: 8

Explanation:

List of Odd length subarrays:

[3] = 3

[5] = 5

Sum of all odd length arrays: 3+5 = 8

Approach 1: Brute Force Solution.

You can quickly get all possible subarrays by running two nested loops but the critical point of this problem is that you need to find only all odd-length subarrays.

You can use a generalized formula that if [(last_position_of_subarray - first_positon_ of _subarray)%2 == 0] then the length is odd else the length is even. You can then add the elements of that subarray to your answer.

C++ Solution Code:

/*C++ code to find sum of odd length subarray*/
#include<bits/stdc++.h>
using namespace std;

int sumOfOddSubarray(vector<int> &num){
    int total = 0;

    for(int i = 0; i < num.size(); i++){
        int sum = 0;
        for(int j = i; j < num.size(); j++){
            sum += num[j];
            if((j - i)%2 == 0)
              total += sum;
        }
    }
    return total;
}

int main(){
    vector<int> num = {1, 3, 2, 5, 6};

    int ans = sumOfOddSubarray(num);
    cout<<"Sum Of Odd Length subarrays: "<<ans;

    return 0;   
}

Output:

Sum Of Odd Length subarrays: 63

Time Complexity: O(n^2)
Space Complexity: O(1)

Approach 2: Using Math.

In the previous approach, you check for all possible subarrays but in this approach, you are going to derive a mathematical formula to solve this problem in O(n) time complexity. This solution might be a little confusing but if you don't give up I am sure you will understand it well. Let's start,

If you observe the question carefully you will find that we only need the sum of subarrays we don't need to print them anywhere so if somehow you count the number of occurrences of each element in all possible odd-length subarray then you can multiply each element with their number of occurrences and sum them up together then you can get your required answer. Let's understand with one example.

In this above example image, we have taken only all odd-length subarrays

Given: [1, 4, 2, 5, 3]

Element      Number of occurance      Sum

ar[0] = 1        3                    1x3 = 3

ar[1] = 4        4                    4x4 = 16

ar[2] = 2        5                    2x5 = 10

ar[3] = 5        4                    5x4 = 20

ar[4] = 3        3                    3x3 = 9

                                    Total = 58

Explanation:

arr[2] = 2 present in 5 times(one time in row first,

three times in row second and one time in row third)

similarly we need to count for all elements.

To create a subarray that contains arr[i] we can take 0, 1, 2, ..... i element on the left hand side from arr[0] to arr[i] and you get (i+1) choices to include arr[i] in the subarray. Similarly, you can take 0, 1, 2, ...... n-1-i element on the right-hand side from arr[i] to arr[n-1]. and you will get (n-i) choices to include arr[i] in the subarray.

In total you will get [k = (i+1)*(n-i)] number of subarrays that contains arr[i] so,

There is (k+1)/2 subarray with the odd length that contains arr[i].

There is (k/2) subarray with even length that contains arr[i].

We can derive a general formula with all the above observations and calculations for finding the number of times an element is occurring for odd-length subarrays.

n = ((i+1)*(n-i)+1)/2

C++ Solution Code:

/*C++ code to find sum of odd length subarray (Optimized)*/
#include<bits/stdc++.h>
using namespace std;

int sumOfOddSubarray(vector<int> &num){
    int total = 0;
    int n = num.size();

    for(int i = 0; i < n; i++){
        total += ((i+1)*(n-i)+1)/2 * num[i];
    }
    return total;
}

int main(){
    vector<int> num = {1, 4, 2, 5, 3};

    int ans = sumOfOddSubarray(num);
    cout<<"Sum Of Odd Length subarrays: "<<ans;

    return 0;   
}

Output:

Sum Of Odd Length subarrays: 58

Time Complexity: O(n)
Space Complexity: O(1)

Program to Find Sum of All Odd Length Subarrays.

Approach 1: Brute Force Solution.

Approach 2: Using Math.

No comments:

Post a Comment