# 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
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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