Given an array arr, the task is to find the total number of subarrays of the given array which do not contain any subarray whose sum of elements is equal to zero. All the array elements may not be distinct.
Examples:
Input: arr = {2, 4, -6}
Output: 5
Explanation:
There are 5 subarrays which do not contain any subarray whose elements sum is equal to zero: [2], [4], [-6], [2, 4], [4, -6]Input: arr = {10, -10, 10}
Output: 3
Naive Approach-
The idea is to find all subarrays and then find those subarrays whose any of the subarrays does not have a sum equal to zero.
Steps to implement-
- Declare a variable count with value 0 to store the final answer
- Run two for loops to find all subarray
- For each subarray find its all subarray by running two another for loops
- If it’s every subarray has a non-zero sum then increment the count
- In the last print the value of the count
Code-
C++
// C++ program to Count the no of subarray// which do not contain any subarray// whose sum of elements is equal to zero#include <bits/stdc++.h>using namespace std;// Function that print the number of// subarrays which do not contain any subarray// whose elements sum is equal to 0void numberOfSubarrays(int arr[], int N){ //To store final answer int count=0; //Find all subarray for(int i=0;i<N;i++){ for(int j=i;j<N;j++){ //Boolean variable to tell whether its any subarray //have sum is equal to zero or not bool val=true; //Find all subarray of this subarray for(int m=i;m<=j;m++){ //To store sum of all elements of subarray int sum=0; for(int n=m;n<=j;n++){ sum+=arr[n]; if(sum==0){ val=false; break; } } if(val==false){break;} } if(val==true){count++;} } } //Print final answer cout<<count<<endl;}// Driver Codeint main(){ int arr[] = { 2, 4, -6 }; int size = sizeof(arr) / sizeof(arr[0]); numberOfSubarrays(arr, size); return 0;} |
Java
public class SubarraySum { // Function that returns the number of subarrays which do not contain // any subarray whose elements sum is equal to 0 public static int numberOfSubarrays(int[] arr, int N) { // To store the final answer int count = 0; // Find all subarrays for (int i = 0; i < N; i++) { for (int j = i; j < N; j++) { // Boolean variable to tell whether any subarray has sum equal to zero or not boolean val = true; // Find all subarrays of this subarray for (int m = i; m <= j; m++) { // To store sum of all elements of subarray int sum = 0; for (int n = m; n <= j; n++) { sum += arr[n]; if (sum == 0) { val = false; break; } } if (!val) { break; } } if (val) { count++; } } } return count; } public static void main(String[] args) { int[] arr = { 2, 4, -6 }; int size = arr.length; int result = numberOfSubarrays(arr, size); System.out.println(result); // This Code Is Contributed By Shubham Tiwari }} |
Python
# Function that returns the number of# subarrays which do not contain any subarray# whose elements sum is equal to 0def numberOfSubarrays(arr): N = len(arr) # To store the final answer count = 0 # Find all subarrays for i in range(N): for j in range(i, N): # Boolean variable to tell whether any subarray # has a sum equal to zero or not val = True # Find all subarrays of this subarray for m in range(i, j+1): s = 0 for n in range(m, j+1): s += arr[n] if s == 0: val = False break if not val: break if val: count += 1 # Return the final answer return count# Driver Codearr = [2, 4, -6]print(numberOfSubarrays(arr))#This Code Is Contributed By Shubham Tiwari |
C#
using System;public class GFG { // Function that print the number of // subarrays which do not contain any subarray // whose elements sum is equal to 0 public static void NumberOfSubarrays(int[] arr, int N) { //To store final answer int count=0; //Find all subarray for(int i=0; i<N; i++){ for(int j=i; j<N; j++){ //Boolean variable to tell whether its any subarray //have sum is equal to zero or not bool val=true; //Find all subarray of this subarray for(int m=i; m<=j; m++){ //To store sum of all elements of subarray int sum=0; for(int n=m; n<=j; n++){ sum += arr[n]; if(sum==0){ val = false; break; } } if(val==false) { break; } } if(val==true) { count++; } } } //Print final answer Console.WriteLine(count); } // Driver Code public static void Main(string[] args) { int[] arr = { 2, 4, -6 }; int size = arr.Length; NumberOfSubarrays(arr, size); // This Code Is Contributed By Shubham Tiwari }} |
Javascript
// Function that prints the number of// subarrays which do not contain any subarray// whose elements sum is equal to 0function numberOfSubarrays(arr) { // To store final answer let count = 0; // Find all subarrays for (let i = 0; i < arr.length; i++) { for (let j = i; j < arr.length; j++) { // Boolean variable to tell whether any subarray // has a sum equal to zero or not let val = true; // Find all subarrays of this subarray for (let m = i; m <= j; m++) { // To store the sum of all elements of subarray let sum = 0; for (let n = m; n <= j; n++) { sum += arr[n]; if (sum === 0) { val = false; break; } } if (val === false) { break; } } if (val === true) { count++; } } } // Print the final answer console.log(count);}// Driver Codeconst arr = [2, 4, -6];numberOfSubarrays(arr);// This code is contributed by rambabuguphka |
Output-
5
Time Complexity: O(N4), because two loops to find all subarray and two more loops to find all subarray of a particular subarray
Auxiliary Space: O(1), because no extra space has been used
Approach:
- Firstly store all elements of array as sum of its previous element.
- Now take two pointers, increase second pointer and store the value in a map while a same element not encounter.
- If an element encounter which is already exist in map, this means there exist a subarray between two pointers whose elements sum is equal to 0.
- Now increase first pointer and remove the element from map while the two same elements exists.
- Store the answer in a variable and finally return it.
Below is the implementation of the above approach:
C++
// C++ program to Count the no of subarray// which do not contain any subarray// whose sum of elements is equal to zero#include <bits/stdc++.h>using namespace std;// Function that print the number of// subarrays which do not contain any subarray// whose elements sum is equal to 0void numberOfSubarrays(int arr[], int n){ vector<int> v(n + 1); v[0] = 0; // Storing each element as sum // of its previous element for (int i = 0; i < n; i++) { v[i + 1] = v[i] + arr[i]; } unordered_map<int, int> mp; int begin = 0, end = 0, answer = 0; mp[0] = 1; while (begin < n) { while (end < n && mp.find(v[end + 1]) == mp.end()) { end++; mp[v[end]] = 1; } // Check if another same element found // this means a subarray exist between // end and begin whose sum // of elements is equal to 0 answer = answer + end - begin; // Erase beginning element from map mp.erase(v[begin]); // Increase begin begin++; } // Print the result cout << answer << endl;}// Driver Codeint main(){ int arr[] = { 2, 4, -6 }; int size = sizeof(arr) / sizeof(arr[0]); numberOfSubarrays(arr, size); return 0;} |
Java
// Java program to Count the no of subarray// which do not contain any subarray// whose sum of elements is equal to zeroimport java.util.*;class GFG{ // Function that print the number of// subarrays which do not contain any subarray// whose elements sum is equal to 0static void numberOfSubarrays(int arr[], int n){ int []v = new int[n + 1]; v[0] = 0; // Storing each element as sum // of its previous element for (int i = 0; i < n; i++) { v[i + 1] = v[i] + arr[i]; } HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); int begin = 0, end = 0, answer = 0; mp.put(0, 1); while (begin < n) { while (end < n && !mp.containsKey(v[end + 1])) { end++; mp.put(v[end], 1); } // Check if another same element found // this means a subarray exist between // end and begin whose sum // of elements is equal to 0 answer = answer + end - begin; // Erase beginning element from map mp.remove(v[begin]); // Increase begin begin++; } // Print the result System.out.print(answer +"\n");} // Driver Codepublic static void main(String[] args){ int arr[] = { 2, 4, -6 }; int size = arr.length; numberOfSubarrays(arr, size);}}// This code is contributed by sapnasingh4991 |
Python3
# Python 3 program to Count the no of subarray# which do not contain any subarray# whose sum of elements is equal to zero# Function that print the number of# subarrays which do not contain any subarray# whose elements sum is equal to 0def numberOfSubarrays(arr, n): v = [0]*(n + 1) # Storing each element as sum # of its previous element for i in range( n): v[i + 1] = v[i] + arr[i] mp = {} begin, end, answer = 0 , 0 , 0 mp[0] = 1 while (begin < n): while (end < n and (v[end + 1]) not in mp): end += 1 mp[v[end]] = 1 # Check if another same element found # this means a subarray exist between # end and begin whose sum # of elements is equal to 0 answer = answer + end - begin # Erase beginning element from map del mp[v[begin]] # Increase begin begin += 1 # Print the result print(answer)# Driver Codeif __name__ == "__main__": arr = [ 2, 4, -6 ] size = len(arr) numberOfSubarrays(arr, size)# This code is contributed by chitranayal |
C#
// C# program to Count the no of subarray// which do not contain any subarray// whose sum of elements is equal to zerousing System;using System.Collections.Generic;class GFG{ // Function that print the number of// subarrays which do not contain any subarray// whose elements sum is equal to 0static void numberOfSubarrays(int []arr, int n){ int []v = new int[n + 1]; v[0] = 0; // Storing each element as sum // of its previous element for (int i = 0; i < n; i++) { v[i + 1] = v[i] + arr[i]; } Dictionary<int,int> mp = new Dictionary<int,int>(); int begin = 0, end = 0, answer = 0; mp.Add(0, 1); while (begin < n) { while (end < n && !mp.ContainsKey(v[end + 1])) { end++; mp.Add(v[end], 1); } // Check if another same element found // this means a subarray exist between // end and begin whose sum // of elements is equal to 0 answer = answer + end - begin; // Erase beginning element from map mp.Remove(v[begin]); // Increase begin begin++; } // Print the result Console.Write(answer +"\n");} // Driver Codepublic static void Main(String[] args){ int []arr = { 2, 4, -6 }; int size = arr.Length; numberOfSubarrays(arr, size);}}// This code is contributed by Rajput-Ji |
Javascript
<script>// JavaScript program to Count the no of subarray// which do not contain any subarray// whose sum of elements is equal to zero// Function that print the number of// subarrays which do not contain any subarray// whose elements sum is equal to 0function numberOfSubarrays(arr, n){ let v = new Array(n + 1); v[0] = 0; // Storing each element as sum // of its previous element for (let i = 0; i < n; i++) { v[i + 1] = v[i] + arr[i]; } let mp = new Map(); let begin = 0, end = 0, answer = 0; mp.set(0, 1); while (begin < n) { while (end < n && !mp.has(v[end + 1])) { end++; mp.set(v[end], 1); } // Check if another same element found // this means a subarray exist between // end and begin whose sum // of elements is equal to 0 answer = answer + end - begin; // Erase beginning element from map mp.clear(); // Increase begin begin++; } // Print the result document.write(answer + "<br>");}// Driver Codelet arr = [ 2, 4, -6 ];let size = arr.length;numberOfSubarrays(arr, size);// This code is contributed by _saurabh_jaiswal</script> |
Output
5
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
