Given an array a, we have to find the minimum product possible with the subset of elements present in the array. The minimum product can be a single element also.
Examples:
Input : a[] = { -1, -1, -2, 4, 3 }
Output : -24
Explanation : Minimum product will be ( -2 * -1 * -1 * 4 * 3 ) = -24
Input : a[] = { -1, 0 }
Output : -1
Explanation : -1(single element) is minimum product possible
Input : a[] = { 0, 0, 0 }
Output : 0
A simple solution is to generate all subsets, find the product of every subset and return the minimum product.
A better solution is to use the below facts.
- If there are even number of negative numbers and no zeros, the result is the product of all except the largest valued negative number.
- If there are an odd number of negative numbers and no zeros, the result is simply the product of all.
- If there are zeros and positive, no negative, the result is 0. The exceptional case is when there is no negative number and all other elements positive then our result should be the first minimum positive number.
PHP
<?php // PHP program to find maximum // product of a subset. // Function to find maximum // product of a subset function minProductSubset($a, $n) { if ($n == 1) return $a[0]; // Find count of negative numbers, // count of zeros, maximum valued // negative number, minimum valued // positive number and product // of non-zero numbers $max_neg = PHP_INT_MIN; $min_pos = PHP_INT_MAX; $count_neg = 0; $count_zero = 0; $prod = 1; for ($i = 0; $i < $n; $i++) { // If number is 0, we don't // multiply it with product. if ($a[$i] == 0) { $count_zero++; continue; } // Count negatives and keep // track of maximum valued // negative. if ($a[$i] < 0) { $count_neg++; $max_neg = max($max_neg, $a[$i]); } // Track minimum positive // number of array if ($a[$i] > 0) $min_pos = min($min_pos, $a[$i]); $prod = $prod * $a[$i]; } // If there are all zeros // or no negative number // present if ($count_zero == $n || ($count_neg == 0 && $count_zero > 0)) return 0; // If there are all positive if ($count_neg == 0) return $min_pos; // If there are even number of // negative numbers and count_neg // not 0 if (!($count_neg & 1) && $count_neg != 0) { // Otherwise result is product of // all non-zeros divided by maximum // valued negative. $prod = $prod / $max_neg; } return $prod; } // Driver code $a = array( -1, -1, -2, 4, 3 ); $n = sizeof($a); echo(minProductSubset($a, $n)); // This code is contributed by Ajit. ?> |
-24
Time Complexity : O(n)
Auxiliary Space : O(1)
Please refer complete article on Minimum product subset of an array for more details!
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
