# Minimum Product Subset of an array

#### algorithm greedy algorithm

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.