Dada una array y un número k, la tarea es calcular la suma del producto de todos los elementos de subarreglos de tamaño k.
Ejemplos:
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
Un enfoque Naive es generar todos los subarreglos de tamaño k y hacer la suma del producto de todos los elementos de los subarreglos.
Implementación:
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 = 3 print(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
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>
Producción
210
Complejidad de tiempo: O(nk)
Un Método Eficiente es utilizar el concepto de Ventana Deslizante .
1- Considere el primer subarreglo/ventana de tamaño k, haga el producto de los elementos y agréguelo a total_sum.
for (i=0; i < k; i++)
prod = prod * arr[i];
2- Ahora, mediante el uso del concepto de ventana deslizante, elimine el primer elemento de la ventana del producto y agregue el siguiente elemento a la ventana. es decir
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- Suma devuelta
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>
Producción
210
Complejidad de tiempo: O(n)
Este artículo es una contribución de Sahil Chhabra . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA