Dado un arreglo de enteros arr de tamaño N , la tarea es imprimir productos de todos los subarreglos del arreglo .
Ejemplos:
Entrada: arr[] = {2, 4}
Salida: 64
Aquí, los subarreglos son [2], [2, 4], [4]
Los productos son 2, 8, 4
Producto de todos los subarreglos = 64Entrada: arr[] = {10, 3, 7}
Salida: 27783000
Aquí, los subarreglos son [10], [10, 3], [10, 3, 7], [3], [3, 7], [7 ]
Los productos son 10, 30, 210, 3, 21, 7
Producto de todos los Subarreglos = 27783000
Enfoque ingenuo: una solución simple es generar todos los subconjuntos y calcular su producto.
C++
// C++ program to find product
// of all subarray of an array
#include <bits/stdc++.h>
using namespace std;
// Function to find product of all subarrays
void product_subarrays(int arr[], int n)
{
// Variable to store the product
int product = 1;
// Compute the product while
// traversing for subarrays
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
for (int k = i; k <= j; k++)
product *= arr[k];
}
}
// Printing product of all subarray
cout << product << "\n";
}
// Driver code
int main()
{
int arr[] = { 10, 3, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
product_subarrays(arr, n);
return 0;
}
Java
// Java program to find product
// of all subarray of an array
import java.util.*;
class GFG {
// Function to find product of all subarrays
static void product_subarrays(int arr[], int n)
{
// Variable to store the product
int product = 1;
// Compute the product while
// traversing for subarrays
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
for (int k = i; k <= j; k++)
product *= arr[k];
}
}
// Printing product of all subarray
System.out.print(product + "\n");
}
// Driver code
public static void main(String args[])
{
int arr[] = { 10, 3, 7 };
int n = arr.length;
// Function call
product_subarrays(arr, n);
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python3 program to find product # of all subarray of an array # Function to find product of all subarrays def product_subarrays(arr, n): # Variable to store the product product = 1; # Compute the product while # traversing for subarrays for i in range(0, n): for j in range(i, n): for k in range(i, j + 1): product *= arr[k]; # Printing product of all subarray print(product, "\n"); # Driver code arr = [ 10, 3, 7 ]; n = len(arr); # Function call product_subarrays(arr, n); # This code is contributed by Code_Mech
C#
// C# program to find product
// of all subarray of an array
using System;
class GFG {
// Function to find product of all subarrays
static void product_subarrays(int[] arr, int n)
{
// Variable to store the product
int product = 1;
// Compute the product while
// traversing for subarrays
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
for (int k = i; k <= j; k++)
product *= arr[k];
}
}
// Printing product of all subarray
Console.Write(product + "\n");
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 10, 3, 7 };
int n = arr.Length;
// Function call
product_subarrays(arr, n);
}
}
// This code is contributed by shivanisinghss2110
Javascript
<script>
// Javascript program to find product
// of all subarray of an array
// Function to find product of all subarrays
function product_subarrays(arr, n)
{
// Variable to store the product
let product = 1;
// Compute the product while
// traversing for subarrays
for (let i = 0; i < n; i++) {
for (let j = i; j < n; j++) {
for (let k = i; k <= j; k++)
product *= arr[k];
}
}
// Printing product of all subarray
document.write(product + "</br>");
}
let arr = [ 10, 3, 7 ];
let n = arr.length;
// Function call
product_subarrays(arr, n);
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
27783000
Complejidad temporal: O(n 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: un enfoque eficiente es usar dos bucles y calcular los productos mientras se recorren los subarreglos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find product
// of all subarray of an array
#include <bits/stdc++.h>
using namespace std;
// Function to find product of all subarrays
void product_subarrays(long long int arr[], int n)
{
// Variable to store the product
long long int res = 1;
// Compute the product while
// traversing for subarrays
for (int i = 0; i < n; i++) {
long long int product = 1;
for (int j = i; j < n; j++) {
product = product * arr[j];
res *= product;
}
}
// Printing product of all subarray
cout << res << "\n";
}
// Driver code
int main()
{
long long int arr[] = { 10, 3, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
product_subarrays(arr, n);
return 0;
}
Java
// Java program to find product
// of all subarray of an array
import java.util.*;
class GFG {
// Function to find product of all subarrays
static void product_subarrays(int arr[], int n)
{
// Variable to store the product
int res = 1;
// Compute the product while
// traversing for subarrays
for (int i = 0; i < n; i++) {
int product = 1;
for (int j = i; j < n; j++) {
product = product * arr[j];
res *= product;
}
}
// Printing product of all subarray
System.out.println(res + "\n");
}
// Driver code
public static void main(String args[])
{
int arr[] = { 10, 3, 7 };
int n = arr.length;
// Function call
product_subarrays(arr, n);
}
}
// This code is contributed by AbhiThakur
Python3
# Python3 program to find product # of all subarray of an array # Function to find product of all subarrays def product_subarrays(arr, n): # Variable to store the product res = 1; # Compute the product while # traversing for subarrays for i in range(n): product = 1 for j in range(i, n): product *= arr[j]; res = res * product # Printing product of all subarray print(res); # Driver code if __name__ == '__main__': arr = [ 10, 3, 7 ]; n = len(arr); # Function call product_subarrays(arr, n); # This code is contributed by Princi Singh
C#
// C# program to find product
// of all subarray of an array
using System;
class GFG {
// Function to find product of all subarrays
static void product_subarrays(int[] arr, int n)
{
// Variable to store the product
int res = 1;
// Compute the product while
// traversing for subarrays
for (int i = 0; i < n; i++) {
int product = 1;
for (int j = i; j < n; j++) {
product *= arr[j];
res = res * product;
}
}
// Printing product of all subarray
Console.WriteLine(res + "\n");
}
// Driver code
public static void Main(String[] args)
{
int[] arr = { 10, 3, 7 };
int n = arr.Length;
// Function call
product_subarrays(arr, n);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to find product
// of all subarray of an array
// Function to find product of all subarrays
function product_subarrays(arr, n)
{
// Variable to store the product
var res = 1;
// Compute the product while
// traversing for subarrays
for (var i = 0; i < n; i++) {
var product = 1;
for (var j = i; j < n; j++) {
product = product * arr[j];
res *= product;
}
}
// Printing product of all subarray
document.write( res );
}
// Driver code
var arr = [10, 3, 7];
var n = arr.length;
// Function call
product_subarrays(arr, n);
</script>
Producción:
27783000
Complejidad temporal: O(n 2 )
Espacio Auxiliar: O(1)