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
A Naive approach is to generate all subarrays of size k and do the sum of product of all elements of subarrays.
Implementation:
C++
// 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; } |
Java
// Java program to find the sum of // product of all subarrays class GFG { // Method to calculate the sum of product static 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 method public static void main(String[] args) { int arr[] = { 1, 2, 3, 4, 5, 6 }; int k = 3; System.out.println(calcSOP(arr, arr.length, k)); } } |
Python3
# python program to find the sum of # product of all subarrays # Function to calculate the sum of product def calcSOP(arr, n, k): # Initialize sum = 0 sum = 0 # Consider every subarray of size k for i in range(0, (n-k)+1): prod = 1 # Calculate product of all elements # of current subarray for j in range(i, k+i): prod = int(prod * arr[j]) # Store sum of all the products sum = sum + prod # Return sum return sum #Driver code arr = [ 1, 2, 3, 4, 5, 6 ] n = len(arr) k = 3print(calcSOP(arr, n, k)) # This code is contributed by Sam007 |
C#
// C# program to find the sum of // product of all subarrays using System; public class GFG { // Method to calculate the sum of product static 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 method public static void Main() { int[] arr = {1, 2, 3, 4, 5, 6}; int k = 3; Console.WriteLine(calcSOP(arr, arr.Length, k)); } } // This code is contributed by Sam007 |
PHP
<?php // PHP program to find the sum of // product of all subarrays // Function to calculate // the sum of product function calcSOP($arr, $n, $k) { // Initialize sum = 0 $sum = 0; // Consider every subarray // of size k for ($i = 0; $i <= $n - $k; $i++) { $prod = 1; // Calculate product of all // elements of current subarray for ($j = $i; $j < $k + $i; $j++) $prod *= $arr[$j]; // Store sum of all // the products $sum += $prod; } // Return sum return $sum; } // Driver code $arr = array( 1, 2, 3, 4, 5, 6 ); $n = count($arr); $k = 3; echo calcSOP($arr, $n, $k); // This code is contributed by Sam007 ?> |
Javascript
<script> // Javascript program to find the sum of // product of all subarrays // Function to calculate // the sum of product function calcSOP(arr, n, k) { // Initialize sum = 0 let sum = 0; // Consider every subarray // of size k for (let i = 0; i <= n - k; i++) { let prod = 1; // Calculate product of all // elements of current subarray for (let j = i; j < k + i; j++) prod *= arr[j]; // Store sum of all // the products sum += prod; } // Return sum return sum; } // Driver code let arr = new Array(1, 2, 3, 4, 5, 6); let n = arr.length; let k = 3; document.write(calcSOP(arr, n, k)); // This code is contributed by gfgking </script> |
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++
// C++ program to find the sum of // product of all subarrays #include <iostream> using namespace std; // Method 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; } // 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; } // This code is contributed by avijitmondal1998. |
Java
// Java program to find the sum of // product of all subarrays class GFG { // Method to calculate the sum of product static 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; } // Driver method public static void main(String[] args) { int arr[] = { 1, 2, 3, 4, 5, 6 }; int k = 3; System.out.println(calcSOP(arr, arr.length, k)); } } |
Python3
# Python3 program to find the sum of # product of all subarrays # Function to calculate the sum of product def calcSOP(arr, n, k): # Initialize sum = 0 and prod = 1 sum = 0 prod = 1 # Consider first subarray of size k # Store the products of elements for i in range(k): 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 i in range(k, n, 1): # 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 int(sum) # Drivers code arr = [1, 2, 3, 4, 5, 6] n = len(arr) k = 3 print(calcSOP(arr, n, k)) # This code is contributed 29AjayKumar |
C#
// C# program to find the sum of // product of all subarrays using System; public class GFG { // Method to calculate the sum of product static 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; } // Driver method public static void Main() { int[] arr = { 1, 2, 3, 4, 5, 6 }; int k = 3; // Function calling Console.WriteLine(calcSOP(arr, arr.Length, k)); } } // This code is contributed by Sam007 |
PHP
<?php // php program to find the sum of // product of all subarrays // Function to calculate the sum of product function calcSOP($arr, $n, $k) { // Initialize sum = 0 and prod = 1 $sum = 0; $prod = 1; // Consider first subarray of size k // Store the products of elements for ($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 ($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 $arr = array( 1, 2, 3, 4, 5, 6 ); $n = count($arr); $k = 3; echo calcSOP($arr, $n, $k); // This code is contributed by Sam007 ?> |
Javascript
<script> // JavaScript program for the above approach function calcSOP(arr,n,k) { // Initialize sum = 0 and prod = 1 let sum = 0, prod = 1; // Consider first subarray of size k // Store the products of elements for (let 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 (let i = k; i < n; i++) { // Divide by the first element // of previous subarray/ window // and product with the current element prod = (Math.floor(prod / arr[i - k])) * arr[i]; // Add current product to the sum sum += prod; } // Return sum return sum; } // Driver method let arr= [1, 2, 3, 4, 5, 6 ]; let k = 3; document.write(calcSOP(arr, arr.length, k)); // This code is contributed by Potta Lokesh </script> |
Output
210
Time Complexity: O(n)
This article is contributed by Sahil Chhabra. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
