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;
}
}
#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.