Given an array of positive and negative numbers. Find if there is a subarray (of size at-least one) with 0 sum.
Example 1:
Input:
5
4 2 -3 1 6
Output:
Yes
Explanation:
2, -3, 1 is the subarray
with sum 0.
This is similar to the previous question Subarray sum equals k but this is EASY compared to that.
To solve this question click here:(https://practice.geeksforgeeks.org/problems/subarray-with-0-sum-1587115621/1/)
Approach 1:
Time Complexity: O(n^2)
JAVA CODE
public static boolean subArrayExists(int arr[],int n)
{
for(int i=0;i<n;i++)
{
int sum=0;
for(int j=i;j<n;j++)
{
sum+=arr[j];
if(sum==0)
return true;
}
}
return false;
}
Approach 2:
This is similar to the previous subarray question that we solved.
Time Complexity: O(n)
JAVA CODE
static boolean findsum(int arr[],int n)
{
//Your code here
HashMap<Integer,Integer> hm=new HashMap<>();
hm.put(0,1); // it is imp to put 0 initially in the hashmap
int sum=0;
for(int i=0;i<n;i++)
{
sum+=arr[i];
if(hm.containsKey(sum))
return true;
hm.put(sum,hm.getOrDefault(sum,0)+1);
}
return false;
}
Approach 3:
We have used HashSet in this as their is no need to use HashMap since we have no use of storing values in key, pair
Time Complexity: O(n)
JAVA CODE
public static boolean subArrayExists(int arr[],int n)
{
//declare a set data structure
HashSet<Integer> res=new HashSet<>();
int sum=0;
for(int i=0;i<n;i++)
{
res.add(sum);//in first step it will add 0
sum+=arr[i];
if(res.contains(sum))
return true;
}
return false;
}
Top comments (0)