Max Product Subset

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
17 upvotes
Asked in companies
AdobeSalesforceArcesium

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
6
-3 -3 -6 -1 -5 2
6
1 2 9 -90 6 4
Sample Output 1:
540
432
Explanation of sample input 1 :
Test Case 1:

In the first test case, we will take the numbers {-3,-3,-6,-5,2} whose product is 540. We can verify that out of all possible subsets; this is the maximum product subset.


Test Case 2:

In the second test case, we will take {1,2,9,6,4} whose product is 432.
Sample Input 2:
2
4
0 1 0 -1 
4
2 4 9 8
Sample Output 2:
1
576
Hint

We can include every positive number in the product and may exclude one negative number if their count is odd.

Approaches (1)
Implementation

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’.
Time Complexity

O(n), where n is the number of elements in the array.

 

We need to traverse the array once to find the maximum product. Hence the complexity is in order of n.

Space Complexity

O(1) we are using constant space.

 

As we are using constant space, hence space complexity is O(1)

Code Solution
(100% EXP penalty)
Max Product Subset
Full screen
Console