Dada una array a[] de tamaño N . El valor de un subconjunto es el producto de los números primos de ese subconjunto. Se considera que un no primo es 1 al encontrar un subproducto de valor. La tarea es encontrar el producto del valor de todos los subconjuntos posibles.
Ejemplos:
Entrada: a[] = {3, 7}
Salida: 20
Los subconjuntos son: {3} {7} {3, 7}
{3, 7} = 3 * 7 = 21
{3} = 3
{7} = 7
21 * 3 * 7 = 441
Entrada: a[] = {10, 2, 14, 3}
Salida: 1679616
Enfoque ingenuo : un enfoque ingenuo es encontrar todos los subconjuntos usando el conjunto potencia y luego encontrar el producto multiplicando todos los valores del subconjunto. El cebado se puede comprobar con Sieve .
Complejidad de tiempo : O(2 N )
Enfoque eficiente : Un enfoque eficiente es resolver el problema usando la observación. Si escribimos todas las subsecuencias, un punto común de observación es que cada número aparece 2 (N – 1) veces en un subconjunto y por lo tanto conducirá al 2 (N-1) como contribución al producto. Iterar a través de la array y verificar si el elemento de la array es primo o no. Si es primo, entonces su contribución es arr[i]2(N-1) veces a la respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the product of
// the multiplication of
// prime numbers in all possible subsets.
#include <bits/stdc++.h>
using namespace std;
// Sieve method to check prime or not
void sieve(int n, vector<bool>& prime)
{
// Initially mark all primes
for (int i = 2; i <= n; i++)
prime[i] = true;
prime[0] = prime[1] = false;
// Iterate and mark all the
// non primes as false
for (int i = 2; i <= n; i++) {
if (prime[i]) {
// Multiples of prime marked as false
for (int j = i * i; j <= n; j += i) {
prime[j] = false;
}
}
}
}
// Function to find the sum
// of sum of all the subset
int sumOfSubset(int a[], int n)
{
// Get the maximum element
int maxi = *max_element(a, a + n);
// Declare a sieve array
vector<bool> prime(maxi + 1);
// Sieve function called
sieve(maxi, prime);
// Number of times an element
// contributes to the answer
int times = pow(2, n - 1);
int sum = 1;
// Iterate and check
for (int i = 0; i < n; i++) {
// If prime
if (prime[a[i]])
sum = sum * (pow(a[i], times)); // Contribution
}
return sum;
}
// Driver Code
int main()
{
int a[] = { 3, 7 };
int n = sizeof(a) / sizeof(a[0]);
cout << sumOfSubset(a, n);
}
Java
// Java program to find the product of
// the multiplication of
// prime numbers in all possible subsets.
import java.util.*;
class GFG
{
// Sieve method to check prime or not
static void sieve(int n, boolean []prime)
{
// Initially mark all primes
for (int i = 2; i <= n; i++)
prime[i] = true;
prime[0] = prime[1] = false;
// Iterate and mark all the
// non primes as false
for (int i = 2; i <= n; i++)
{
if (prime[i])
{
// Multiples of prime marked as false
for (int j = i * i; j <= n; j += i)
{
prime[j] = false;
}
}
}
}
// Function to find the sum
// of sum of all the subset
static int sumOfSubset(int a[], int n)
{
// Get the maximum element
int maxi = Arrays.stream(a).max().getAsInt();
// Declare a sieve array
boolean []prime = new boolean[maxi + 1];
// Sieve function called
sieve(maxi, prime);
// Number of times an element
// contributes to the answer
int times = (int) Math.pow(2, n - 1);
int sum = 1;
// Iterate and check
for (int i = 0; i < n; i++)
{
// If prime
if (prime[a[i]])
sum = (int) (sum * (Math.pow(a[i], times)));
}
return sum;
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 3, 7 };
int n = a.length;
System.out.println(sumOfSubset(a, n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to find the product of # the multiplication of # prime numbers in all possible subsets. prime = [True for i in range(100)] # Sieve method to check prime or not def sieve(n, prime): # Initially mark all primes for i in range(1, n + 1): prime[i] = True prime[0] = prime[1] = False # Iterate and mark all the # non primes as false for i in range(2, n + 1): if (prime[i]): # Multiples of prime marked as false for j in range(2 * i, n + 1, i): prime[j] = False # Function to find the Sum # of Sum of all the subset def SumOfSubset(a, n): # Get the maximum element maxi = max(a) # Declare a sieve array # Sieve function called sieve(maxi, prime) # Number of times an element # contributes to the answer times = pow(2, n - 1) Sum = 1 # Iterate and check for i in range(n): # If prime if (prime[a[i]]): Sum = Sum * (pow(a[i], times)) # Contribution return Sum # Driver Code a = [3, 7] n = len(a) print(SumOfSubset(a, n)) # This code is contributed # by Mohit Kumar
C#
// C# program to find the product of
// the multiplication of
// prime numbers in all possible subsets.
using System;
using System.Linq;
class GFG
{
// Sieve method to check prime or not
static void sieve(int n, Boolean []prime)
{
// Initially mark all primes
for (int i = 2; i <= n; i++)
prime[i] = true;
prime[0] = prime[1] = false;
// Iterate and mark all the
// non primes as false
for (int i = 2; i <= n; i++)
{
if (prime[i])
{
// Multiples of prime marked as false
for (int j = i * i; j <= n; j += i)
{
prime[j] = false;
}
}
}
}
// Function to find the sum
// of sum of all the subset
static int sumOfSubset(int []a, int n)
{
// Get the maximum element
int maxi = a.Max();
// Declare a sieve array
Boolean []prime = new Boolean[maxi + 1];
// Sieve function called
sieve(maxi, prime);
// Number of times an element
// contributes to the answer
int times = (int) Math.Pow(2, n - 1);
int sum = 1;
// Iterate and check
for (int i = 0; i < n; i++)
{
// If prime
if (prime[a[i]])
sum = (int) (sum * (Math.Pow(a[i], times)));
}
return sum;
}
// Driver Code
public static void Main(String[] args)
{
int []a = { 3, 7 };
int n = a.Length;
Console.WriteLine(sumOfSubset(a, n));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// javascript program to find the product of
// the multiplication of
// prime numbers in all possible subsets.
// Sieve method to check prime or not
function sieve(n, prime)
{
// Initially mark all primes
for (var i = 2; i <= n; i++)
prime[i] = true;
prime[0] = prime[1] = false;
// Iterate and mark all the
// non primes as false
for (i = 2; i <= n; i++)
{
if (prime[i])
{
// Multiples of prime marked as false
for (j = i * i; j <= n; j += i) {
prime[j] = false;
}
}
}
}
// Function to find the sum
// of sum of all the subset
function sumOfSubset(a , n) {
// Get the maximum element
var maxi = Math.max.apply(Math,a);
// Declare a sieve array
var prime =Array(maxi + 1).fill(0);
// Sieve function called
sieve(maxi, prime);
// Number of times an element
// contributes to the answer
var times = parseInt( Math.pow(2, n - 1));
var sum = 1;
// Iterate and check
for (i = 0; i < n; i++) {
// If prime
if (prime[a[i]])
sum = parseInt( (sum * (Math.pow(a[i], times))));
}
return sum;
}
// Driver Code
var a = [ 3, 7 ];
var n = a.length;
document.write(sumOfSubset(a, n));
// This code is contributed by umadevi9616
</script>
441
Complejidad de tiempo : O(M log M) para precálculo donde M es el elemento máximo y O(N) para iteración.
Complejidad espacial : O(M)
Nota : Como arr[i] 2(N-1) puede ser realmente grande, la respuesta puede desbordarse, es preferible usar operaciones de tipo de datos y mod más grandes para conservar la respuesta.