Last Updated: 13 Feb, 2021
Max Product Subset
Moderate
Asked in companies
You are given an array/list ‘arr’ of size ‘n’. Your task is to find the maximum product possible by taking any subset of the array/list ‘arr’.
Since the product can be large, return it modulo 10^9+7
For example:
Let arr=[-1,-1,-2,4,3]
We can take the subset {-1,-2,4,3} which will have the product as 24. We can verify that this is the largest product possible. Hence we return 24.
Input Format:
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test cases follow.
The first line of each test case contains ‘n’ denoting the number of elements in arr.
The second line of each test case contains ‘n’ space-separated integers denoting the elements of ‘arr’
Output Format
For each test case, return an integer with the product of the subset with the largest product.
Output for each test case will be printed in a separate line.
Note:
1. You do not need to print anything; it has already been taken care of. Just implement the given function.
2. It is guaranteed that the maximum product will be less than or equal to 10^18.
Constraints:
1 <= T <= 50
1 <= N <= 10^4
-10^2 <= arr[i] <=10^2
Where ‘T’ is the total number of test cases and N denotes the size of arr1 and arr[i] represents the value of any number in arr
Time limit: 1 second
Approaches
The key idea in solving this problem is to realize that the product of positive numbers is always increasing. Also, the product of even numbers of negatives also increases our result.
So, we can conclude all the points as :
- If the array consists of only positive numbers, taking all of them as excluding them will always decrease the product.
- If the array has an even number of negative elements, Take all of them, as the product of an even number of negative numbers is positive.
- If the array has an odd number of negative elements, just take all of them except one whose magnitude is the least.
- If there are zeroes always ignore them, UNLESS the array only contains zeroes and a single negative number, in that case, the answer will be zero. Also, if the array consists of only zeros, the answer will be zero.
Note that in the case of an odd number of negative numbers, there can be multiple elements whose magnitude is the least but we need to exclude only one of them.
Algorithm:
- If ‘N’ is equal to 1, return the only element in the array.
- Initialize ‘ans’ to 1.
- Initialize ‘id’ to -1 and ‘minElement’ to 0.
- Initialize ‘negCount’ and ‘zeroCount’ to 0.
- Iterate through the array
- If current element is 0, increment ‘zeroCount’ by 1.
- If current element is negative
- Increment ‘negCount’ by 1.
- If ‘id’ is equal to -1 or the magnitude of the current element is smaller than ‘minElement’, assign ‘minElment’ to the current element and ‘id’ to the current index.
- If ‘zeroCount’ is equal to ‘N’
- Return 0
- If ‘negCount’ is equal to 1 and ‘zeroCount’ is equal to ‘N’ - 1
- Return 0
- Iterate through the array
- If current element is zero, continue.
- If ‘negCount’ is odd and the current index is equal to ‘id’, continue.
- Else update ‘ans’ to the product of ‘ans’ and current element mod 1^9 + 7.
- Return ‘ans’.
Similar problems