Count of subarray that does not contain any subarray with sum 0

0 0 9 minutes read

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 0
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
   cout<<count<<endl;
}
 
// Driver Code
int 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 0
def 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 Code
arr = [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 0
function 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 Code
const arr = [2, 4, -6];
numberOfSubarrays(arr);
 
// This code is contributed by rambabuguphka

Output-

Time Complexity: O(N⁴), 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 0
void 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 Code
int 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 zero
import java.util.*;
 
class GFG{
  
// Function that print the number of
// subarrays which do not contain any subarray
// whose elements sum is equal to 0
static 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 Code
public 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 0
def 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 Code
if __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 zero
using 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 0
static 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 Code
public 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 0
function 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 Code
 
let arr = [ 2, 4, -6 ];
let size = arr.length;
 
numberOfSubarrays(arr, size);
 
// This code is contributed by _saurabh_jaiswal
 
</script>

Output

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 zambiatek!