Get this book -> Problems on Array: For Interviews and Competitive Programming

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:

- Generate all subsets of the array.
- Calculate the product of all the elements over the subset.
- 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:

- If there are an odd number of negative numbers, the result is the product of all non-zero numbers.
- 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.
- If there are zeros and no negative numbers, the result is zero.
- 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.