Sum of product of all elements of sub-arrays of size k

Given an array and a number k, the task is to calculate the sum of the product of all elements of subarrays of size k.

Examples:

Input : arr[] = {1, 2, 3, 4, 5, 6} 
            k = 3
Output : 210
Consider all subarrays of size k
1*2*3 = 6
2*3*4 = 24
3*4*5 = 60
4*5*6 = 120
6 + 24 + 60 + 120 = 210

Input : arr[] = {1, -2, 3, -4, 5, 6} 
            k = 2
Output : -10
Consider all subarrays of size k
1*-2 = -2
-2*3 = -6
3*-4 = -12
-4*5 = -20
5*6  =   30
-2 + -6 + -12 + -20+ 30 = -10

Naive approach is to generate all subarrays of size k and do the sum of product of all elements of subarrays.

// C++ program to find the sum of
// product of all subarrays
#include <iostream>
using namespace std;
// Function to calculate the sum of product
int calcSOP(int arr[], int n, int k)
{
    // Initialize sum = 0
    int sum = 0;
    // Consider every subarray of size k
    for (int i = 0; i <= n - k; i++) {
        int prod = 1;
        // Calculate product of all elements
        // of current subarray
        for (int j = i; j < k + i; j++)
            prod *= arr[j];
        // Store sum of all the products
        sum += prod;
    }
    // Return sum
    return sum;
}
// Driver code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << calcSOP(arr, n, k);
    return 0;
}

Output:

210

Time Complexity: O(nk)

 

An Efficient Method is to use the concept of Sliding Window.

1- Consider first subarray/window of size k, do the product of elements and add to the total_sum.

 for (i=0; i < k; i++)
       prod = prod * arr[i];

2- Now, By Using sliding window concept, remove first element of window from the product and add next element to the window. i.e.

for (i =k ; i < n; i++)
 {
     // Removing first element from product  
     prod = prod / arr[i-k]; 

     //  Adding current element to the product
     prod = prod * arr[i];  
     sum += prod;
 }

3- Return sum

// C++ program to find the sum of
// product of all subarrays
#include <iostream>
using namespace std;
// Function to calculate the sum of product
int calcSOP(int arr[], int n, int k)
{
    // Initialize sum = 0 and prod = 1
    int sum = 0, prod = 1;
    // Consider first subarray of size k
    // Store the products of elements
    for (int i = 0; i < k; i++)
        prod *= arr[i];
    // Add the product to the sum
    sum += prod;
    // Consider every subarray of size k
    // Remove first element and add current
    // element to the window
    for (int i = k; i < n; i++) {
        // Divide by the first element
        // of previous subarray/ window
        // and product with the current element
        prod = (prod / arr[i - k]) * arr[i];
        // Add current product to the sum
        sum += prod;
    }
    // Return sum
    return sum;
}
// Drivers code
int main()
{
    int arr[] = { 1, 2, 3, 4, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << calcSOP(arr, n, k);
    return 0;

Output:

210

Time Complexity: O(n)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/sum-product-elements-sub-arrays-size-k/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

http://www.techcodebit.com. #techcodebit #google #microsoft #facebook #interview portal #jobplacements
#technicalguide

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar