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.
Solução
Obrigado pelo seu feedback!
single
Pergunte à IA
Pergunte à IA
Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo
Resumir este capítulo
Explicar o código em file
Explicar por que file não resolve a tarefa
Awesome!
Completion rate improved to 7.69
Minimum Product Subset
Deslize para mostrar o 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.
Solução
Obrigado pelo seu feedback!
Awesome!
Completion rate improved to 7.69single