PROBLEM LINK:
Author: Pradeep Kumar Sahu
Tester: Gaurav Kumar
Pratyaksh Gupta
Editorialist: Pradeep Kumar Sahu
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Basic observations, Math
PROBLEM:
Given an array A[ \ ] = \{ A_1 , A_2 , A_3 , \dots ,A_N \} and a number N (length of array) .
Find the minimum length of non-empty sub-sequence of the array such that the product of all numbers in the subsequence will be maximum. (Minimum sub-sequence size is 1)
EXPLANATION:
In the given problem we have to minimize the length of the sub-sequence so that product of all the number in sub-sequence will be maximum.
Include all the positive number > 1 in the subsequence for the maximum product.
Do not include 1 in the subsequence because it will only make our subsequence length more and the product still remains the same.
Also do not include 0 in the subsequence because it will make our product = 0.
If array A[ \ ] also have negative number which is less than -1 then try to include the numbers in the pair so that we get positive product. (negative * negative = positive)
After including all the negative number which is less than -1 in the paired form, if any negative number < -1 still left then find -1 in the array A[ \ ].
If A[ \ ] contain -1 then take only one -1 and include both the number (-1 , number < -1 ) and if A[ \ ] does not contain -1 then do not include that negative number in the subsequence.
SOLUTIONS:
Setter's Solution / Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int min_length(int a[] , int n){
if(n == 1)
return 1;
//IT WILL BE BETTER TO REMOVE ALL THE 1 AND 0 FROM THE ARRAY BECAUSE 1 WILL ONLY INCREASE OUR SUBSEQUENCE LENGTH AND IT WILL HAVE NO EFFECT ON THE PRODUCT , SIMILARLY 0 WILL MAKE PRODUCT 0 BUT WE NEED MAXPRODUCT
vector<int>v;
for(int i=0 ; i<n;i++)
{
if(a[i] == 0 || a[i] == 1)
continue;
else
v.push_back(a[i]);
}
//If all the element in the array is 1 and/or 0 then the max_product of the subsequence will always be either 0 or 1 and in this case min_length will be 1
if(v.size() == 0)
return 1;
//If single element is left then min_length = 1
if(v.size() == 1)
return 1;
int ct_negative_num_except_minus_one = 0;
int ct_minus_one = 0;
int ct_positve_num = 0;
for(int i=0 ; i<v.size() ; i++){
if(v[i] < -1)
ct_negative_num_except_minus_one++;
else if(v[i] == -1)
ct_minus_one++;
else
ct_positve_num++;
}
//WE HAVE TO INCLUDE ALL THE POSITIVE NUMBER IN THE SUBSEQUENCE TO GET THE MAX PRODUCT
//Here vector size > 1 and if all the element in the vector is -1 then the max product will -1 * -1 = 1 , so in this case the min length will be 2
if(ct_minus_one == v.size())
return 2;
//If ct_negative_num_except_minus_one is even then there is no need to include -1 in the subsequence
if(ct_negative_num_except_minus_one % 2 == 0)
return ct_positve_num + ct_negative_num_except_minus_one;
else {
//If ct_negative_num_except_minus_one is odd , then it means the sequence we have taken have product negative so to make product maximum we have to either include one -1 to the product so that the product become positive and maximun or if we don't have extra -1 then it will be better to remove one negative number from the subsequence so that product become positive and maximum
if(ct_minus_one > 0)
return ct_positve_num + ct_negative_num_except_minus_one + 1;
else
return ct_positve_num + ct_negative_num_except_minus_one - 1;
}
}
int main() {
int t;
cin >> t;
while(t--)
{
int n ;
cin >> n;
int a[n];
for(int i=0 ; i<n; i++)
cin >> a[i];
int ans = min_length(a , n);
cout << ans << endl;
}
}
Tester's Solution (Gaurav Kumar)
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int arr[n];
vector<int> neg;
int count=0,kk=0,cc=0,zero=0;
for(int i=0;i<n;i++)
{
cin>>arr[i];
if(arr[i]>1)
count++;
else if(arr[i]<-1)
neg.push_back(arr[i]);
else if(arr[i]==-1)
kk++;
else if(arr[i]==1)
cc++;
else if(arr[i]==0)
zero++;
}
if(neg.size()>0){
if(neg.size()%2==0)
cout<<count+neg.size()<<endl;
else
{
if(kk>0)
{
cout<<count+neg.size()+1<<endl;
}
else
{
cout<<count+neg.size()-1<<endl;
}
}
}
else
{
if(count==0)
{
if(cc>0)
cout<<1<<endl;
else if(kk>=2)
cout<<2<<endl;
else if(kk==1)
cout<<1<<endl;
else if(zero>0)
cout<<1<<endl;
}
else
cout<<count<<endl;
}
}
return 0;
}
Tester's Solution (Pratyaksh Gupta)
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// your code goes here
int test;
cin>>test;
while(test--){
int n;
cin>>n;
vector<int>arr(n);
for(int i=0;i<n;i++)
cin>>arr[i];
if(n==1){
cout<<"1\n";
continue;
}
int negativeNumber=0,positiveNumber=0;
int negativeOne=0,positiveOne=0;
for(int i=0;i<n;i++){
if(arr[i]<-1)
negativeNumber++;
else if(arr[i]>1)
positiveNumber++;
else if(arr[i]==-1)
negativeOne++;
else if(arr[i]==1)
positiveOne++;
}
if(negativeNumber%2==1){
if(negativeOne>0){
negativeNumber++;
negativeOne--;
}
else
negativeNumber--;
}
if(negativeNumber+positiveNumber==0&&positiveOne>0)
positiveNumber++;
if(negativeNumber+positiveNumber==0&&negativeOne>1)
negativeNumber+=2;
if(negativeNumber+positiveNumber==0)
cout<<"1\n";
else
cout<<negativeNumber+positiveNumber<<endl;
}
return 0;
}