Étant donné un tableau a, nous devons trouver le produit minimum possible avec le sous-ensemble d'éléments présents dans le tableau. Le produit minimum peut également être un élément unique.

Exemples: 

Entrée : a[] = { -1, -1, -2, 4, 3 }
 Sortie : -24
 Explication : Le produit minimum sera ( -2 * -1 * -1 * 4 * 3 ) = -24

Entrée : a[] = { -1, 0 }
 Sortie : -1
 Explication : -1(élément unique) est le produit minimum possible
 
Entrée : a[] = { 0, 0, 0 }
 Sortie : 0

Une solution simple consiste à générer tous les sous-ensembles, à trouver le produit de chaque sous-ensemble et à renvoyer le produit minimum.
Une meilleure solution consiste à utiliser les faits ci-dessous.  

  1. S'il y a un nombre pair de nombres négatifs et pas de zéros, le résultat est le produit de tous sauf le plus grand nombre négatif.
  2. S'il y a un nombre impair de nombres négatifs et pas de zéros, le résultat est simplement le produit de tous.
  3. S'il y a des zéros et du positif, pas de négatif, le résultat est 0. Le cas exceptionnel est lorsqu'il n'y a pas de nombre négatif et que tous les autres éléments sont positifs, alors notre résultat devrait être le premier nombre positif minimum.

// 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;
}
Complexité temporelle : ONon 
Espace auxiliaire : O(1)


Modifié le: mardi 16 août 2022, 19:28