NONNEGPROD - Editorial

PROBLEM LINK:

Contest
Practice

Setter: munch_01
Testers: tabr
Editorialist: aryanag_adm

DIFFICULTY:

948

PREREQUISITES:

None

PROBLEM:

You are given a list of N integers A_1, A_2, \cdots, A_n.

Output the minimum number of integers you can remove from the list so that their product is \geq 0.

EXPLANATION:

\prod_{i=1}^n A_i < 0 if and only if A has an odd number of negative integers and does not have 0.

If \prod_{i=1}^n A_i < 0, we can remove any negative integer from A. The remaining list will have an even number of negative integers, and will therefore have non negative product. In this case the answer is 1.

Else, we do not need to remove anything, and the answer is 0.

We can implement this approach with some counters for the number of negative integers and the number of zeroes, along with some simple if-else statements.

TIME COMPLEXITY:

Time complexity is O(N).

SOLUTION:

Editorialist's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#include <sys/resource.h>
#define double long double
#define int long long
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define MOD 1000000007
#define INF 1000000000
#define mid(l, u) ((l+u)/2)
#define rchild(i) (i*2 + 2)
#define lchild(i) (i*2 + 1)
#define mp(a, b) make_pair(a, b)
#define lz lazup(l, u, i);
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin>>t;
    while(t--) {
        int n;
        cin>>n;
        int a[n];
        int ans = 0;
        bool z = 0;
        for(int i = 0;i<n;i++){
            cin>>a[i];
            ans = ans ^ (a[i] < 0);
            z = z || (a[i] == 0);
        }
        cout<<(ans && !z)<<endl;
    }

}

Why my code was wrong?

#include <iostream>
using namespace std;
void pro(int x)
{
    int j;
    int product = 1;
    int a[x];
    for(j=0;j<x;j++)
    {
        cin >> a[j];
        product = product * a[j];
    }
    if(product < 0 )
    cout << '1' << endl;
    else
    cout << '0' << endl;
}
int main() {
    int n,i,x;
    cin >> n;
    for(i=0;i<n;i++)
    {
        cin >> x;
        pro(x);
    }
	return 0;
}

1 Like

The product is too large to compute, you are getting an integer overflow I think.

I did the same thing finding product and checking if it is " >=0 " or not, it didn’t work for me too.

I too implemented a product based solution. What’s going wrong here?

#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--)
    {
        long n;
        int negatives=0;
        int number;
        cin>>n;
        for(int i=0;i<n;i++){
            cin >> number;
            if(number==0){
                std::cout << 0 << std::endl;
            }
            if(number < 0){
                negatives++;
            }
        }
        
        if(negatives % 2 == 0){
            return 0;
        }
        
        else
            return 1;
        
    }
	return 0;
}

I dont know why this code does not work. it passes one of the 2 test cases.

#include <bits/stdc++.h>
#define ll int long long
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define sp ' '
#define nl '\n'
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin >> t;
	while(t--) {
	    int n , count = 0;
	    bool contains_zero = false;
	    cin >> n;
	    
	    for(int i = 0 ; i < n ; i ++) {
	        int temp;
	        cin >> temp;
	        
	        if (temp == 0) {
	            contains_zero = true;
	            break;
	        }
	        
	        if (temp < 0)
	            count ++;
	    }
	    if (!contains_zero)
	        cout << (count % 2) << nl;
	    else
	        cout << 0 << nl;
	}
	return 0;
}

I keep getting a runtime error (SIGSEGV) and i cant understand what it is and why im getting it

#include <iostream>
using namespace std;

int main() {
    int t,n;
    int i, cnt=0;
    cin>>t;
    int arr[n];
    int ans[t];
   while(t--)
    {
        cin>>n;
        
        for (int j=0;j<n;j++){
               cin>>arr[j];
         if (arr[j]<0)
            {
                cnt++;
                
            }
          if (arr[j]==0)
         {
             cnt==0;
         }    
         //cout<<"cnt="<<cnt<<endl;
         
        
       }    
         if (cnt%2==0 || cnt==0)
            {
                //cout<<"1"<<endl;
                ans[i]=0;
                cout<<ans[i]<<endl;
            } else if (cnt%2!=0 || cnt==1)
            {
                //cout<<"0"<<endl;
                ans[i]=1;
                cout<<ans[i]<<endl;
            }
         
    }
    
	return 0;
}

I rarely do anything with cpp. But I am rather certain you get this error, because you do not initialize one of your arrays:

int arr[n];

Since n=0 at this point of time, you should have an empty array I assume. You can try to access and store stuff in this array, you may override data or you may get blocked by trying to access RAM you are not allowed to access. This should be the reason you get the SIGSEGV error.

The fix:

int arr[10000];