Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar el producto del máximo de todos los subconjuntos posibles de la array dada . Dado que el producto puede ser muy grande, imprímalo en módulo (10 9 + 7) .
Ejemplos:
Entrada: arr[] = {1, 2, 3}
Salida:
Explicación:
Todos los subconjuntos posibles de la array dada con sus respectivos elementos máximos son:
- {1}, el elemento máximo es 1.
- {2}, el elemento máximo es 2.
- {3}, el elemento máximo es 3.
- {1, 2}, el elemento máximo es 2.
- {1, 3}, el elemento máximo es 3.
- {2, 3}, el elemento máximo es 3.
- {1, 2, 3}, el elemento máximo es 3.
El producto de todo el elemento máximo anterior es 1*2*3*2*3*3*3 = 324.
Entrada: arr[] = {1, 1, 1, 1}
Salida: 1
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los subconjuntos posibles de la array dada y encontrar el producto del máximo de todos los subconjuntos generados módulo (10 9 + 7) como el producto resultante.
Complejidad temporal: O(N*2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar en función de las siguientes observaciones:
- La idea es contar el número de veces que aparece cada elemento del arreglo como el elemento máximo entre todos los subconjuntos posibles formados.
- Un elemento de array arr[i] es un máximo si y solo si todos los elementos excepto arr[i] son menores o iguales que él.
- Por lo tanto, el número de subconjuntos formados por todos los elementos menores o iguales a cada elemento del arreglo arr[i] contribuye al recuento de subconjuntos que tienen arr[i] como elemento máximo.
Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos maximoProducto como 1 que almacene el producto resultante del máximo de elementos de todos los subconjuntos.
- Ordene la array dada arr[] en orden creciente.
- Recorra la array desde el final usando la variable i y realice los siguientes pasos:
- Encuentra el número de subconjuntos que son más pequeños que el elemento actual arr[i] como (2 i – 1) y guárdalo en una variable, digamos P .
- Dado que el elemento de array arr[i] contribuye P número de veces, multiplique el valor arr[i] , P veces por la variable producto máximo .
- Encuentre el producto del elemento de array con MaximumProduct para incluir todos los subconjuntos de tamaño 1 .
- Después de completar los pasos anteriores, imprima el valor de producto máximo como el producto máximo resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the product of the
// maximum of all possible subsets
long maximumProduct(int arr[], int N)
{
long mod = 1000000007;
// Sort the given array arr[]
sort(arr, arr + N);
// Stores the power of 2
long power[N + 1];
power[0] = 1;
// Calculate the power of 2
for (int i = 1; i <= N; i++) {
power[i] = 2 * power[i - 1];
power[i] %= mod;
}
// Stores the resultant product
long result = 1;
// Traverse the array from the back
for (int i = N - 1; i > 0; i--) {
// Find the value of 2^i - 1
long value = (power[i] - 1);
// Iterate value number of times
for (int j = 0; j < value; j++) {
// Multiply value with
// the result
result *= 1LL * arr[i];
result %= mod;
}
}
// Calculate the product of array
// elements with result to consider
// the subset of size 1
for (int i = 0; i < N; i++) {
result *= 1LL * arr[i];
result %= mod;
}
// Return the resultant product
return result;
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
cout << maximumProduct(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.Arrays;
class GFG{
// Function to find the product of the
// maximum of all possible subsets
static long maximumProduct(int arr[], int N)
{
long mod = 1000000007;
// Sort the given array arr[]
Arrays.sort(arr);
// Stores the power of 2
long power[] = new long[N + 1];
power[0] = 1;
// Calculate the power of 2
for(int i = 1; i <= N; i++)
{
power[i] = 2 * power[i - 1];
power[i] %= mod;
}
// Stores the resultant product
long result = 1;
// Traverse the array from the back
for(int i = N - 1; i > 0; i--)
{
// Find the value of 2^i - 1
long value = (power[i] - 1);
// Iterate value number of times
for(int j = 0; j < value; j++)
{
// Multiply value with
// the result
result *= arr[i];
result %= mod;
}
}
// Calculate the product of array
// elements with result to consider
// the subset of size 1
for(int i = 0; i < N; i++)
{
result *= arr[i];
result %= mod;
}
// Return the resultant product
return result;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 2, 3 };
int N = arr.length;
System.out.println(maximumProduct(arr, N));
}
}
// This code is contributed by rishavmahato348
Python3
# Python3 program for the above approach # Function to find the product of the # maximum of all possible subsets def maximumProduct(arr, N): mod = 1000000007 # Sort the given array arr[] arr = sorted(arr) # Stores the power of 2 power = [0] * (N + 1) power[0] = 1 # Calculate the power of 2 for i in range(1, N + 1): power[i] = 2 * power[i - 1] power[i] %= mod # Stores the resultant product result = 1 # Traverse the array from the back for i in range(N - 1, -1, -1): # Find the value of 2^i - 1 value = (power[i] - 1) # Iterate value number of times for j in range(value): # Multiply value with # the result result *= arr[i] result %= mod # Calculate the product of array # elements with result to consider # the subset of size 1 for i in range(N): result *= arr[i] result %= mod # Return the resultant product return result # Driver Code if __name__ == '__main__': arr = [ 1, 2, 3 ] N = len(arr) print(maximumProduct(arr, N)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the product of the
// maximum of all possible subsets
static long maximumProduct(int []arr, int N)
{
long mod = 1000000007;
// Sort the given array arr[]
Array.Sort(arr);
// Stores the power of 2
long []power = new long[N + 1];
power[0] = 1;
// Calculate the power of 2
for (int i = 1; i <= N; i++) {
power[i] = 2 * power[i - 1];
power[i] %= mod;
}
// Stores the resultant product
long result = 1;
// Traverse the array from the back
for (int i = N - 1; i > 0; i--) {
// Find the value of 2^i - 1
long value = (power[i] - 1);
// Iterate value number of times
for (int j = 0; j < value; j++) {
// Multiply value with
// the result
result *= 1 * arr[i];
result %= mod;
}
}
// Calculate the product of array
// elements with result to consider
// the subset of size 1
for (int i = 0; i < N; i++) {
result *= 1 * arr[i];
result %= mod;
}
// Return the resultant product
return result;
}
// Driver Code
public static void Main()
{
int []arr = {1, 2, 3};
int N = arr.Length;
Console.Write(maximumProduct(arr, N));
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the product of the
// maximum of all possible subsets
function maximumProduct(arr, N)
{
let mod = 1000000007;
// Sort the given array arr[]
arr.sort((a, b) => a - b);
// Stores the power of 2
let power = new Array(N + 1);
power[0] = 1;
// Calculate the power of 2
for (let i = 1; i <= N; i++) {
power[i] = 2 * power[i - 1];
power[i] %= mod;
}
// Stores the resultant product
let result = 1;
// Traverse the array from the back
for (let i = N - 1; i > 0; i--) {
// Find the value of 2^i - 1
let value = (power[i] - 1);
// Iterate value number of times
for (let j = 0; j < value; j++) {
// Multiply value with
// the result
result *= 1 * arr[i];
result %= mod;
}
}
// Calculate the product of array
// elements with result to consider
// the subset of size 1
for (let i = 0; i < N; i++) {
result *= 1 * arr[i];
result %= mod;
}
// Return the resultant product
return result;
}
// Driver Code
let arr = [1, 2, 3 ];
let N = arr.length;
document.write(maximumProduct(arr, N));
</script>
Producción:
324
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikey134 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA