Subarray with 0 sum
PROBLEM :
Given an array of positive and negative numbers, find if there is a subarray (of size at-least one) with 0 sum.
Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains an integer n denoting the size of the array. The next line contains n space separated integers forming the array.
Output:
Print "Yes" ( without quotes) if there exist a subarray of size at least one with sum equal to 0 or else print "No" ( without quotes).
Constraints:
1<=T<=100
1<=n<=10^4
-10^5<=a[i]<=10^5
Example:
Input:
2
5
4 2 -3 1 6
5
4 2 0 1 6
Output:
Yes
Yes
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
#include<iostream>
#include <bits/stdc++.h>
#include<unordered_set>
using namespace std;
int main()
{
int t ;
cin>>t ;
while(t--)
{
int no ;
cin>>no ;
int arr[no] ;
for(int i=0;i<no;i++)
cin>>arr[i] ;
unordered_set<int> set ;
int sum=0 ;
bool flag=false ;
for(int i=0;i<no;i++)
{
sum+=arr[i] ;
if(sum==0||set.find(sum)!=set.end())
{
flag=true ;
break ;
}
else
set.insert(sum) ;
}
if(flag)
cout<<"Yes" ;
else
cout<<"No" ;
cout<<endl ;
}
return 0;
}
--------------------------------------------------------------------------------
Given an array of positive and negative numbers, find if there is a subarray (of size at-least one) with 0 sum.
Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains an integer n denoting the size of the array. The next line contains n space separated integers forming the array.
Output:
Print "Yes" ( without quotes) if there exist a subarray of size at least one with sum equal to 0 or else print "No" ( without quotes).
Constraints:
1<=T<=100
1<=n<=10^4
-10^5<=a[i]<=10^5
Example:
Input:
2
5
4 2 -3 1 6
5
4 2 0 1 6
Output:
Yes
Yes
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------
#include<iostream>
#include <bits/stdc++.h>
#include<unordered_set>
using namespace std;
int main()
{
int t ;
cin>>t ;
while(t--)
{
int no ;
cin>>no ;
int arr[no] ;
for(int i=0;i<no;i++)
cin>>arr[i] ;
unordered_set<int> set ;
int sum=0 ;
bool flag=false ;
for(int i=0;i<no;i++)
{
sum+=arr[i] ;
if(sum==0||set.find(sum)!=set.end())
{
flag=true ;
break ;
}
else
set.insert(sum) ;
}
if(flag)
cout<<"Yes" ;
else
cout<<"No" ;
cout<<endl ;
}
return 0;
}
--------------------------------------------------------------------------------
Comments
Post a Comment