Minimum Product Subset of an array

Reading time: 20 minutes

For a given array of elements, we have to find the non-empty subset having the minimum product. We will explore two techniques:

• brute force O(2^N)
• Greedy algorithm O(N)

Example

Given an array { 1, -1, 2, 0, -10, -2}

The subset {1, -1, 2, -10, -2} will have the maximum product that is -40.

All other subsets will have product greater than -40.

Naive Approach O(2^N)

A naive approach would be to generate all subsets of the array of length N and calculating the product for each of them. Since generating all subsets takes exponential time, this approach is very inefficient.

The steps involved are:

1. Generate all subsets of the array.
2. Calculate the product of all the elements over the subset.
3. Update the minimum value of the product.

Pseudocode:

Input: Set[], set_size
1. Get the size of power set
    powet_set_size = pow(2, set_size)
    min_product = INT_MAX
2  Loop for counter from 0 to pow_set_size
     (a) Loop for i = 0 to set_size
          (i) Initialize product_temp to 1
          (ii) If ith bit in counter is set
               Print ith element from set for this subset
               Update product_temp by multiplying with  ith element
          (iii) Set max_product to min(min_product, product_temp)
     (b) Print seperator for subsets i.e., newline

Algorithm O(N)

We can come up with a better solution if we pay attention to the following:

1. If there are an odd number of negative numbers, the result is the product of all non-zero numbers.
2. If there are an even number of negative numbers, the result is the product of all non-zero numbers except the largest valued negative number.
3. If there are zeros and no negative numbers, the result is zero.
4. If all numbers are positive, the result is the least valued number

Implementation

#include <bits/stdc++.h>

using namespace std;

int main()
{
    //Taking input of size of array of numbers
    int n;
    cin >> n;

    //Declaring a vector to store the numbers
    vector<int> a(n);

    //Setting variable negative to store maximum valued negative number
    //Setting variable positive to store minimum valued positive number
    int negative = INT_MIN, positive = INT_MAX;

    //Counter variables to store number of zeros and negative numbers
    int countzero = 0, countneg = 0;

    //Initializing product to 1
    int product = 1;

    for(int i=0;i<n;i++){
        //Taking input of elements
        cin >> a[i];

        if(a[i]==0){
            //Incrementing zero counter if input is 0
            countzero++;
        }else if(a[i]<0){
            //Incrementing negative counter if input is <0
            countneg++;
            //Updating negative to maximum valued negative number
            negative = max(negative, a[i]);
        }else{
            //Updating positive to minimum valued positive number
            positive = min(positive, a[i]);
        }
        //Updating product
        product *= a[i];
    }

    if(countzero==n || (countzero>0 && countneg==0)){
        // If there are all zeros or no negative number present
        cout << 0;
    }else if(countneg==0){
        // If there are all positive
        cout << positive;
    }else if(!(countneg%2) && countneg!=0){
        // If there are even number of negative numbers and count_neg not 0
        cout << product/negative;
        //Result is product of all non-zeros divided by maximum valued negative.
    }else{
        cout << product;
    }

    return 0;
}

Examples

Consider the following arrays:

• For the following array, the minimum product is the product of all numbers, i.e., -864 ({-4, -6, -2, 3, 6}):
• For the following array, the minimum product is the minimum number, i.e., -11 ({-11}):
• For the following array, the minimum product is 0 ({0}):
• For the following array, the minimum product is the minimum positive number, i.e., 2 ({2}):
• For the following array, the minimum product is the product of all numbers divided by the maximum valued negative number, i.e., -432 ({4, -6, 3, 6}):

Complexity

The time complexity of this algorithm is O(N), as the array is traversed only once.