Minimum Product Subset
Given an array a
, your goal is to find the minimum product possible with the subset of elements of the array and store it to the variable res
.
Examples
a = [1,8,3,-6,-2,-1]
res
= 1*8*3*(-6)*(-2)*(-1) = -288
a = [-2,-1,0,9]
res
= -2*9=-18
a = [0, 999]
res
= 0
a = [-3, 5]
res
= -3 * 5= -15
Greedy Approach
The goal is to reach the maximum absolute value of the product, i. e. use as many elements as possible until the product is negative. Thus, you have to use an odd number of negative elements of the array. By the way, pay attention to the 0 elements: it makes sense to use it in some cases, although it makes the product equal to 0.
Let’s explore different cases of elements in the array:
- There is at least one negative integer. If you multiply the odd amount of them, you’ll get some negative value, right? So, the goal is to take as many huge negative numbers as possible, but only an odd amount. Pick the maximum odd amount of them, i. e.: if there are 2*n-1 integers, pick them all, else if 2*n – pick them all, and remove one integer with the smallest absolute value. After that, increase the abs value of your
res
by multiplying all positive integers in the array (not 0!) - There are only positive integers: pick the single smallest number, and there is an answer. If you multiply more, you'll increase the result.
- There are only positive integers and 0: think to yourself, what’s your decision?
Following this, you can build an algorithm using these cases.
Swipe to start coding
Fill empty places in the code.
Solution
Merci pour vos commentaires !
single
Demandez à l'IA
Demandez à l'IA
Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion
Résumer ce chapitre
Expliquer le code dans file
Expliquer pourquoi file ne résout pas la tâche
Awesome!
Completion rate improved to 7.69
Minimum Product Subset
Glissez pour afficher le menu
Given an array a
, your goal is to find the minimum product possible with the subset of elements of the array and store it to the variable res
.
Examples
a = [1,8,3,-6,-2,-1]
res
= 1*8*3*(-6)*(-2)*(-1) = -288
a = [-2,-1,0,9]
res
= -2*9=-18
a = [0, 999]
res
= 0
a = [-3, 5]
res
= -3 * 5= -15
Greedy Approach
The goal is to reach the maximum absolute value of the product, i. e. use as many elements as possible until the product is negative. Thus, you have to use an odd number of negative elements of the array. By the way, pay attention to the 0 elements: it makes sense to use it in some cases, although it makes the product equal to 0.
Let’s explore different cases of elements in the array:
- There is at least one negative integer. If you multiply the odd amount of them, you’ll get some negative value, right? So, the goal is to take as many huge negative numbers as possible, but only an odd amount. Pick the maximum odd amount of them, i. e.: if there are 2*n-1 integers, pick them all, else if 2*n – pick them all, and remove one integer with the smallest absolute value. After that, increase the abs value of your
res
by multiplying all positive integers in the array (not 0!) - There are only positive integers: pick the single smallest number, and there is an answer. If you multiply more, you'll increase the result.
- There are only positive integers and 0: think to yourself, what’s your decision?
Following this, you can build an algorithm using these cases.
Swipe to start coding
Fill empty places in the code.
Solution
Merci pour vos commentaires !
Awesome!
Completion rate improved to 7.69single