Dada una array a, tenemos que encontrar el mínimo producto posible con el subconjunto de elementos presentes en la array. El producto mínimo también puede ser un solo elemento.
Ejemplos:
Input : a[] = { -1, -1, -2, 4, 3 }
Output : -24
Explanation : Minimum product will be ( -2 * -1 * -1 * 4 * 3 ) = -24
Input : a[] = { -1, 0 }
Output : -1
Explanation : -1(single element) is minimum product possible
Input : a[] = { 0, 0, 0 }
Output : 0
Una solución simple es generar todos los subconjuntos , encontrar el producto de cada subconjunto y devolver el producto mínimo.
Una mejor solución es usar los siguientes datos.
- Si hay un número par de números negativos y ningún cero, el resultado es el producto de todos excepto el número negativo de mayor valor.
- Si hay un número impar de números negativos y ningún cero, el resultado es simplemente el producto de todos.
- Si hay ceros y positivo, no negativo, el resultado es 0. El caso excepcional es cuando no hay un número negativo y todos los demás elementos positivos, entonces nuestro resultado debe ser el primer número positivo mínimo.
C++
// CPP program to find maximum product of
// a subset.
#include <bits/stdc++.h>
using namespace std;
int minProductSubset(int a[], int n)
{
if (n == 1)
return a[0];
// Find count of negative numbers, count of zeros,
// maximum valued negative number, minimum valued
// positive number and product of non-zero numbers
int max_neg = INT_MIN, min_pos = INT_MAX, count_neg = 0,
count_zero = 0, prod = 1;
for (int i = 0; i < n; i++) {
// If number is 0, we don't multiply it with
// product.
if (a[i] == 0) {
count_zero++;
continue;
}
// Count negatives and keep track of maximum valued
// negative.
if (a[i] < 0) {
count_neg++;
max_neg = max(max_neg, a[i]);
}
// Track minimum positive number of array
if (a[i] > 0)
min_pos = min(min_pos, a[i]);
prod = prod * a[i];
}
// If there are all zeros or no negative number present
if (count_zero == n || (count_neg == 0 && count_zero > 0))
return 0;
// If there are all positive
if (count_neg == 0)
return min_pos;
// If there are even number of negative numbers and
// count_neg not 0
if (!(count_neg & 1) && count_neg != 0)
// Otherwise result is product of all non-zeros
// divided by maximum valued negative.
prod = prod / max_neg;
return prod;
}
int main()
{
int a[] = { -1, -1, -2, 4, 3 };
int n = sizeof(a) / sizeof(a[0]);
cout << minProductSubset(a, n);
return 0;
}
// This code is contributed by Sania Kumari Gupta
C
// C program to find maximum product of
// a subset.
#include <limits.h>
#include <stdio.h>
// Find maximum between two numbers.
int max(int num1, int num2)
{
return (num1 > num2) ? num1 : num2;
}
// Find minimum between two numbers.
int min(int num1, int num2)
{
return (num1 > num2) ? num2 : num1;
}
int minProductSubset(int a[], int n)
{
if (n == 1)
return a[0];
// Find count of negative numbers, count of zeros,
// maximum valued negative number, minimum valued
// positive number and product of non-zero numbers
int max_neg = INT_MIN, min_pos = INT_MAX, count_neg = 0,
count_zero = 0, prod = 1;
for (int i = 0; i < n; i++) {
// If number is 0, we don't multiply it with
// product.
if (a[i] == 0) {
count_zero++;
continue;
}
// Count negatives and keep track of maximum valued
// negative.
if (a[i] < 0) {
count_neg++;
max_neg = max(max_neg, a[i]);
}
// Track minimum positive number of array
if (a[i] > 0)
min_pos = min(min_pos, a[i]);
prod = prod * a[i];
}
// If there are all zeros or no negative number present
if (count_zero == n || (count_neg == 0 && count_zero > 0))
return 0;
// If there are all positive
if (count_neg == 0)
return min_pos;
// If there are even number of negative numbers and
// count_neg not 0
if (!(count_neg & 1) && count_neg != 0)
// Otherwise result is product of all non-zeros
// divided by maximum valued negative.
prod = prod / max_neg;
return prod;
}
int main()
{
int a[] = { -1, -1, -2, 4, 3 };
int n = sizeof(a) / sizeof(a[0]);
printf("%d", minProductSubset(a, n));
return 0;
}
// This code is contributed by Sania Kumari Gupta
Java
// Java program to find maximum product of
// a subset.
class GFG {
static int minProductSubset(int a[], int n)
{
if (n == 1)
return a[0];
// Find count of negative numbers,
// count of zeros, maximum valued
// negative number, minimum valued
// positive number and product of
// non-zero numbers
int negmax = Integer.MIN_VALUE;
int posmin = Integer.MAX_VALUE;
int count_neg = 0, count_zero = 0;
int product = 1;
for (int i = 0; i < n; i++) {
// if number is zero,count it
// but dont multiply
if (a[i] == 0) {
count_zero++;
continue;
}
// count the negative numbers
// and find the max negative number
if (a[i] < 0) {
count_neg++;
negmax = Math.max(negmax, a[i]);
}
// find the minimum positive number
if (a[i] > 0 && a[i] < posmin)
posmin = a[i];
product *= a[i];
}
// if there are all zeroes
// or zero is present but no
// negative number is present
if (count_zero == n
|| (count_neg == 0 && count_zero > 0))
return 0;
// If there are all positive
if (count_neg == 0)
return posmin;
// If there are even number except
// zero of negative numbers
if (count_neg % 2 == 0 && count_neg != 0) {
// Otherwise result is product of
// all non-zeros divided by maximum
// valued negative.
product = product / negmax;
}
return product;
}
// main function
public static void main(String[] args)
{
int a[] = { -1, -1, -2, 4, 3 };
int n = 5;
System.out.println(minProductSubset(a, n));
}
}
// This code is contributed by Arnab Kundu.
Python3
# Python3 program to find maximum
# product of a subset.
# def to find maximum
# product of a subset
def minProductSubset(a, n):
if (n == 1):
return a[0]
# Find count of negative numbers,
# count of zeros, maximum valued
# negative number, minimum valued
# positive number and product
# of non-zero numbers
max_neg = float('-inf')
min_pos = float('inf')
count_neg = 0
count_zero = 0
prod = 1
for i in range(0, n):
# If number is 0, we don't
# multiply it with product.
if (a[i] == 0):
count_zero = count_zero + 1
continue
# Count negatives and keep
# track of maximum valued
# negative.
if (a[i] < 0):
count_neg = count_neg + 1
max_neg = max(max_neg, a[i])
# Track minimum positive
# number of array
if (a[i] > 0):
min_pos = min(min_pos, a[i])
prod = prod * a[i]
# If there are all zeros
# or no negative number
# present
if (count_zero == n or (count_neg == 0
and count_zero > 0)):
return 0
# If there are all positive
if (count_neg == 0):
return min_pos
# If there are even number of
# negative numbers and count_neg
# not 0
if ((count_neg & 1) == 0 and
count_neg != 0):
# Otherwise result is product of
# all non-zeros divided by
# maximum valued negative.
prod = int(prod / max_neg)
return prod
# Driver code
a = [-1, -1, -2, 4, 3]
n = len(a)
print(minProductSubset(a, n))
# This code is contributed by
# Manish Shaw (manishshaw1)
C#
// C# program to find maximum product of
// a subset.
using System;
public class GFG {
static int minProductSubset(int[] a, int n)
{
if (n == 1)
return a[0];
// Find count of negative numbers,
// count of zeros, maximum valued
// negative number, minimum valued
// positive number and product of
// non-zero numbers
int negmax = int.MinValue;
int posmin = int.MinValue;
int count_neg = 0, count_zero = 0;
int product = 1;
for (int i = 0; i < n; i++) {
// if number is zero, count it
// but dont multiply
if (a[i] == 0) {
count_zero++;
continue;
}
// count the negative numbers
// and find the max negative number
if (a[i] < 0) {
count_neg++;
negmax = Math.Max(negmax, a[i]);
}
// find the minimum positive number
if (a[i] > 0 && a[i] < posmin) {
posmin = a[i];
}
product *= a[i];
}
// if there are all zeroes
// or zero is present but no
// negative number is present
if (count_zero == n
|| (count_neg == 0 && count_zero > 0))
return 0;
// If there are all positive
if (count_neg == 0)
return posmin;
// If there are even number except
// zero of negative numbers
if (count_neg % 2 == 0 && count_neg != 0) {
// Otherwise result is product of
// all non-zeros divided by maximum
// valued negative.
product = product / negmax;
}
return product;
}
// main function
public static void Main()
{
int[] a = new int[] { -1, -1, -2, 4, 3 };
int n = 5;
Console.WriteLine(minProductSubset(a, n));
}
}
// This code is contributed by Ajit.
PHP
<?php
// PHP program to find maximum
// product of a subset.
// Function to find maximum
// product of a subset
function minProductSubset($a, $n)
{
if ($n == 1)
return $a[0];
// Find count of negative numbers,
// count of zeros, maximum valued
// negative number, minimum valued
// positive number and product
// of non-zero numbers
$max_neg = PHP_INT_MIN;
$min_pos = PHP_INT_MAX;
$count_neg = 0; $count_zero = 0;
$prod = 1;
for ($i = 0; $i < $n; $i++)
{
// If number is 0, we don't
// multiply it with product.
if ($a[$i] == 0)
{
$count_zero++;
continue;
}
// Count negatives and keep
// track of maximum valued
// negative.
if ($a[$i] < 0)
{
$count_neg++;
$max_neg = max($max_neg, $a[$i]);
}
// Track minimum positive
// number of array
if ($a[$i] > 0)
$min_pos = min($min_pos, $a[$i]);
$prod = $prod * $a[$i];
}
// If there are all zeros
// or no negative number
// present
if ($count_zero == $n ||
($count_neg == 0 &&
$count_zero > 0))
return 0;
// If there are all positive
if ($count_neg == 0)
return $min_pos;
// If there are even number of
// negative numbers and count_neg
// not 0
if (!($count_neg & 1) &&
$count_neg != 0)
{
// Otherwise result is product of
// all non-zeros divided by maximum
// valued negative.
$prod = $prod / $max_neg;
}
return $prod;
}
// Driver code
$a = array( -1, -1, -2, 4, 3 );
$n = sizeof($a);
echo(minProductSubset($a, $n));
// This code is contributed by Ajit.
?>
Javascript
<script>
// Javascript program to find maximum
// product of a subset.
function minProductSubset(a, n)
{
if (n == 1)
return a[0];
// Find count of negative numbers,
// count of zeros, maximum valued
// negative number, minimum valued
// positive number and product of
// non-zero numbers
let negmax = Number.MIN_VALUE;
let posmin = Number.MIN_VALUE;
let count_neg = 0, count_zero = 0;
let product = 1;
for(let i = 0; i < n; i++)
{
// If number is zero, count it
// but dont multiply
if (a[i] == 0)
{
count_zero++;
continue;
}
// Count the negative numbers
// and find the max negative number
if (a[i] < 0)
{
count_neg++;
negmax = Math.max(negmax, a[i]);
}
// Find the minimum positive number
if (a[i] > 0 && a[i] < posmin)
{
posmin = a[i];
}
product *= a[i];
}
// If there are all zeroes
// or zero is present but no
// negative number is present
if (count_zero == n || (count_neg == 0 &&
count_zero > 0))
return 0;
// If there are all positive
if (count_neg == 0)
return posmin;
// If there are even number except
// zero of negative numbers
if (count_neg % 2 == 0 && count_neg != 0)
{
// Otherwise result is product of
// all non-zeros divided by maximum
// valued negative.
product = parseInt(product / negmax, 10);
}
return product;
}
// Driver code
let a = [ -1, -1, -2, 4, 3 ];
let n = 5;
document.write(minProductSubset(a, n));
// This code is contributed by rameshtravel07
</script>
Producción:
-24
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por Surya Priy y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA