PROBLEM LINK:
Author: Kanhaiya Mohan
Tester: Divyansh Tyagi
Editorialist:Shivam Thakur, Akshit Dhoundiyal
DIFFICULTY
Easy
PREREQUESITES
Array, Greedy
PROBLEM:
From a given array of size n we have to select k element of which the product is minimum.
EXPLANATION :
Case I : If n=k, then we have to select all the element and the required product is the product of given array.
Case II : When we have to find k elements and all elements in the array are positive and non zero.
In that case we have to select k smallest element. For this arrange the element in ascending
order and take the product of the first k element.
Case III : When we have to find k element when all element in the array is either positive
and at least one is zero .
In this case we can select at least one zero element and we can select any (k-1) element from
the array. Then the minimum product came to be 0.
Case IV : When we have to select an odd ‘k’ element when all the elements are negative.
In this case, we have to select that element which have greatest magnitude for this we can
arrange the negative array in ascending order and select the last ‘k’ element. In this way the product
will be minimum with negative magnitude.
Case V : When we have to select even ‘k’ elements when all elements are negative.
In this case, we have to arrange the negative array in ascending order and select last ‘k’
elements, so that the magnitude of the selected element is smallest. Hence the required
minimum product will be the product of the first ‘k’ element of the negative array.
Case VI : When all elements are either positive or negative and we have to find an odd ‘k’ element.
In this case we have to select the largest negative element first, then we have to select either
pairwise negative or pairwise positive largest elements. So, that the
product gets maximised in negative.
Note: In this case if in the given array 0 is present and the product is positive then take the product as zero as we can take zero and get our product to be zero.
For example: Take array [-5,-4,-3,4,5] as given array. And we have to select 3 elements from this.
So, we have to first split this array into two arrays named negative and positive array. In negative
array [-5,-4,-3] and in positive [4,5]. So, according to above explanation first element we have to
select is -5 from negative array. Because -5 is the largest negative element. After that we have two
pairs to select the remaining two elements that are [-4,-3] and [4,5] from this we can select [4,5].
Because the product of 4 and 5 is 20 which is more than the product of -4 and -3. Hence the 3
selected elements is [-5,4,5] and their product is -100 is minimum.
Case VII: When all elements are either positive or negative and we have to find even ‘k’ elements.
In this case, first we will select, minimum negative number and a maximum positive number and then we have to select pairwise negative or positive elements such that their product is smaller than other such combinations.
Note: In this case if in the given array 0 is present and the product is positive then take the product as zero as we can take zero and get our product to be zero.
For example: Take array [-5,-4,-3,4,5] as given array. And we have to select 4 elements from this.
So, according to above explanations first we have to select the smallest number from the negative array so we can select -5 and then largest number from positive array so we can select 5 and now we can select pairwise negative or positive number for this we have only one set that is [-4,-3]. So, we have our selected element set is [-5,5,-4,-3] and it’s product is -300 which is the least product.
Solution :
Setter’s Solution
#include <bits/stdc++.h>
using namespace std;
#define sync
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
#define rep(n) for (int i = 0; i < n; i++)
#define rep1(a, b) for (int i = a; i < b; i++)
#define int long long int
#define mod 1000000007
int n, k;
void solve()
{
cin >> n >> k;
vector<int> neg, pos;
bool zero = false;
rep(n)
{
int x;
cin >> x;
if (x < 0)
{
neg.push_back(x);
}
else if (x > 0)
{
pos.push_back(x);
}
else
{
zero = true;
}
}
sort(pos.rbegin(), pos.rend()); //sort pos in decreasing order
sort(neg.begin(), neg.end()); //sort neg in increasing order
//check if answer will be zero
if ((neg.size() + pos.size() < k) || ((neg.size() == 0) && (zero))
||
((pos.size() == 0) && (zero) && (k % 2 == 0)))
{
cout << 0;
return;
}
//check if answer will be positive: smallest k positive elements or largest k negative elements
if (neg.size() == 0)
{
int ans = 1;
for (int i = pos.size() - 1, cnt = 0; cnt < k; i--, cnt++)
{
ans *= pos[i];
}
cout << ans;
return;
}
if (pos.size() == 0 && k % 2 == 0)
{
int ans = 1;
for (int i = neg.size() - 1, cnt = 0; cnt < k; i--, cnt++)
{
ans *= neg[i];
}
cout << ans;
return;
}
//now the answer will be definitely negative
int ans = 1;
int i, j;
if (k % 2)
{
ans = neg[0];
k--;
i = 1;
j = 0;
}
else
{
ans = neg[0] *pos[0];
k -= 2;
i = 1;
j = 1;
}
while (k)
{
int p1 = -1;
int p2 = -1;
if (i + 1 < neg.size())
{
p1 = neg[i] *neg[i + 1];
}
if (j + 1 < pos.size())
{
p2 = pos[j] *pos[j + 1];
}
if (p1 > p2)
{
ans *= p1;
i += 2;
}
else
{
ans *= p2;
j += 2;
}
k -= 2;
}
if (zero)
ans = min(0 LL, ans);
cout << ans;
}
int32_t main()
{
#
ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#
endif
sync;
int t = 1;
cin >> t;
while (t--)
{
solve();
cout << "\n";
}
return 0;
}