Producto de todos los subarreglos de un arreglo | conjunto 2

Dado un arreglo arr[] de enteros de tamaño N , la tarea es encontrar los productos de todos los subarreglos del arreglo .
Ejemplos: 
 

Entrada: arr[] = {2, 4} 
Salida: 64 
Explicación: 
Aquí, los subarreglos son {2}, {2, 4} y {4}. 
Los productos de cada subarreglo son 2, 8, 4. 
Producto de todos los subarreglos = 64
Entrada: arr[] = {1, 2, 3} 
Salida: 432 
Explicación: 
Aquí, los subarreglos son {1}, {1, 2}, { 1, 2, 3}, {2}, {2, 3}, {3}. 
Los productos de cada subarreglo son 1, 2, 6, 2, 6, 3. 
Producto de todos los subarreglos = 432 
 

Enfoque ingenuo e iterativo: Consulte esta publicación para conocer estos enfoques.
Enfoque: La idea es contar el número de cada elemento que ocurre en todos los subarreglos. Para contar tenemos las siguientes observaciones: 
 

• En cada subarreglo que comienza con arr[i] , hay (N – i) tales subconjuntos que comienzan con el elemento arr[i] . 
  Por ejemplo: 
   

Para array arr[] = {1, 2, 3} 
N = 3 y para el elemento 2, es decir, índice = 1 
Hay (N – índice) = 3 – 1 = 2 subconjuntos 
{2} y {2, 3} 
 

•  
• Para cualquier elemento arr[i] , hay (N – i)*i subarreglos donde arr[i] no es el primer elemento. 
   

Para array arr[] = {1, 2, 3} 
N = 3 y para el elemento 2, es decir, índice = 1 
Hay (N – índice)*índice = (3 – 1)*1 = 2 subconjuntos donde 2 no es el primer elemento 
{1, 2} y {1, 2, 3} 
 

Por lo tanto, a partir de las observaciones anteriores, el número total de cada elemento arr[i] ocurre en todos los subarreglos en cada índice i viene dado por: 
 

total_elements = (N - i) + (N - i)*i
total_elements = (N - i)*(i + 1) 

La idea es multiplicar cada elemento (N – i)*(i + 1) varias veces para obtener el producto de los elementos en todos los subarreglos.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the product of
// elements of all subarray
long int SubArrayProdct(int arr[],
                        int n)
{
    // Initialize the result
    long int result = 1;
 
    // Computing the product of
    // subarray using formula
    for (int i = 0; i < n; i++)
        result *= pow(arr[i],
                      (i + 1) * (n - i));
 
    // Return the product of all
    // elements of each subarray
    return result;
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int arr[] = { 2, 4 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << SubArrayProdct(arr, N)
         << endl;
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the product of
// elements of all subarray
static int SubArrayProdct(int arr[], int n)
{
     
    // Initialize the result
    int result = 1;
 
    // Computing the product of
    // subarray using formula
    for(int i = 0; i < n; i++)
       result *= Math.pow(arr[i], (i + 1) *
                                  (n - i));
 
    // Return the product of all
    // elements of each subarray
    return result;
}
 
// Driver code
public static void main(String[] args)
{
 
    // Given array arr[]
    int arr[] = new int[]{2, 4};
 
    int N = arr.length;
 
    // Function Call
    System.out.println(SubArrayProdct(arr, N));
}
}
 
// This code is contributed by Pratima Pandey

# Python3 program for the above approach
 
# Function to find the product of
# elements of all subarray
def SubArrayProdct(arr, n):
 
    # Initialize the result
    result = 1;
 
    # Computing the product of
    # subarray using formula
    for i in range(0, n):
        result *= pow(arr[i],
                     (i + 1) * (n - i));
 
    # Return the product of all
    # elements of each subarray
    return result;
 
# Driver Code
 
# Given array arr[]
arr = [ 2, 4 ];
N = len(arr);
 
# Function Call
print(SubArrayProdct(arr, N))
 
# This code is contributed by Code_Mech

// C# program for the above approach
using System;
class GFG{
 
// Function to find the product of
// elements of all subarray
static int SubArrayProdct(int []arr, int n)
{
     
    // Initialize the result
    int result = 1;
 
    // Computing the product of
    // subarray using formula
    for(int i = 0; i < n; i++)
       result *= (int)(Math.Pow(arr[i], (i + 1) *
                                        (n - i)));
 
    // Return the product of all
    // elements of each subarray
    return result;
}
 
// Driver code
public static void Main()
{
 
    // Given array arr[]
    int []arr = new int[]{2, 4};
 
    int N = arr.Length;
 
    // Function Call
    Console.Write(SubArrayProdct(arr, N));
}
}
 
// This code is contributed by Code_Mech

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to find the product of
// elements of all subarray
function SubArrayProdct(arr, n)
{
       
    // Initialize the result
    let result = 1;
   
    // Computing the product of
    // subarray using formula
    for(let i = 0; i < n; i++)
       result *= Math.pow(arr[i], (i + 1) *
                                  (n - i));
   
    // Return the product of all
    // elements of each subarray
    return result;
}
 
// Driver code
 
     // Given array arr[]
    let arr = [2, 4];
   
    let N = arr.length;
   
    // Function Call
    document.write(SubArrayProdct(arr, N));
  
 // This code is contributed by sanjoy_62.
</script>

64

Complejidad temporal: O(N) , donde N es el número de elementos. 
Espacio Auxiliar: O(1)