Count subarrays with non-zero sum in the given Array

Given an array arr[] of size N, the task is to count the total number of subarrays for the given array arr[] which have a non-zero-sum.
Examples:

Input: arr[] = {-2, 2, -3} 
Output: 4 
Explanation: 
The subarrays with non zero sum are: [-2], [2], [2, -3], [-3]. All possible subarray of the given input array are [-2], [2], [-3], [2, -2], [2, -3], [-2, 2, -3]. Out of these [2, -2] is not included in the count because 2+(-2) = 0 and [-2, 2, -3] is not selected because one the subarray [2, -2] of this array has a zero sum of elements.
Input: arr[] = {1, 3, -2, 4, -1} 
Output: 15 
Explanation: 
There are 15 subarray for the given array {1, 3, -2, 4, -1} which has a non zero sum.

Approach:
The main idea to solve the above question is to use the Prefix Sum Array and Map Data Structure.

• First, build the Prefix sum array of the given array and use the below formula to check if the subarray has 0 sum of elements.

Sum of Subarray[L, R] = Prefix[R] – Prefix[L – 1]. So, If Sum of Subarray[L, R] = 0
Then, Prefix[R] – Prefix[L – 1] = 0. Hence, Prefix[R] = Prefix[L – 1] 
 

• Now, iterate from 1 to N and keep a Hash table for storing the index of the previous occurrence of the element and a variable let's say last, and initialize it to 0.
• Check if Prefix[i] is already present in the Hash or not. If yes then, update last as last = max(last, hash[Prefix[i]] + 1). Otherwise, Add i - last to the answer and update the Hash table.

Below is the implementation of the above approach:

// C++ program to Count the total number of  // subarrays for a given array such that its  // subarray should have non zero sum #include <bits/stdc++.h> using namespace std; // Function to build the Prefix sum array vector<int> PrefixSumArray(int arr[], int n) {  vector<int> prefix(n);  // Store prefix of the first position  prefix[0] = arr[0];  for (int i = 1; i < n; i++)  prefix[i] = prefix[i - 1] + arr[i];  return prefix; } // Function to return the Count of // the total number of subarrays int CountSubarray(int arr[], int n) {  vector<int> Prefix(n);  // Calculating the prefix array  Prefix = PrefixSumArray(arr, n);  int last = 0, ans = 0;  map<int, int> Hash;  Hash[0] = -1;  for (int i = 0; i <= n; i++) {  // Check if the element already exists  if (Hash.count(Prefix[i]))  last = max(last, Hash[Prefix[i]] + 1);  ans += max(0, i - last);  // Mark the element  Hash[Prefix[i]] = i;  }  // Return the final answer  return ans; } // Driver code int main() {  int arr[] = { 1, 3, -2, 4, -1 };  int N = sizeof(arr) / sizeof(arr[0]);  cout << CountSubarray(arr, N); } 

// Java program to count the total number of  // subarrays for a given array such that its  // subarray should have non zero sum import java.util.*; class GFG{ // Function to build the Prefix sum array static int[] PrefixSumArray(int arr[], int n) {  int []prefix = new int[n];    // Store prefix of the first position  prefix[0] = arr[0];  for(int i = 1; i < n; i++)  prefix[i] = prefix[i - 1] + arr[i];  return prefix; } // Function to return the Count of // the total number of subarrays static int CountSubarray(int arr[], int n) {  int []Prefix = new int[n];  // Calculating the prefix array  Prefix = PrefixSumArray(arr, n);  int last = 0, ans = 0;  HashMap<Integer,  Integer> Hash = new HashMap<Integer,  Integer>();  Hash.put(0, -1);  for(int i = 0; i <= n; i++)   {    // Check if the element already exists  if (i < n && Hash.containsKey(Prefix[i]))  last = Math.max(last,   Hash.get(Prefix[i]) + 1);  ans += Math.max(0, i - last);  // Mark the element  if (i < n)  Hash.put(Prefix[i], i);  }  // Return the final answer  return ans; } // Driver code public static void main(String[] args) {  int arr[] = { 1, 3, -2, 4, -1 };  int N = arr.length;  System.out.print(CountSubarray(arr, N)); } } // This code is contributed by amal kumar choubey 

# Python3 program to count the total number  # of subarrays for a given array such that  # its subarray should have non zero sum  # Function to build the prefix sum array  def PrefixSumArray(arr, n): prefix = [0] * (n + 1); # Store prefix of the first position  prefix[0] = arr[0]; for i in range(1, n): prefix[i] = prefix[i - 1] + arr[i]; return prefix; # Function to return the count of  # the total number of subarrays  def CountSubarray(arr, n): Prefix = [0] * (n + 1); # Calculating the prefix array  Prefix = PrefixSumArray(arr, n); last = 0; ans = 0; Hash = {}; Hash[0] = -1; for i in range(n + 1): # Check if the element already exists  if (Prefix[i] in Hash): last = max(last, Hash[Prefix[i]] + 1); ans += max(0, i - last); # Mark the element  Hash[Prefix[i]] = i; # Return the final answer  return ans; # Driver code  if __name__ == "__main__" : arr = [ 1, 3, -2, 4, -1 ]; N = len(arr); print(CountSubarray(arr, N)); # This code is contributed by AnkitRai01 

// C# program to count the total number of  // subarrays for a given array such that its  // subarray should have non zero sum using System; using System.Collections.Generic; class GFG{ // Function to build the Prefix sum array static int[] PrefixSumArray(int []arr, int n) {  int []prefix = new int[n];    // Store prefix of the first position  prefix[0] = arr[0];  for(int i = 1; i < n; i++)  prefix[i] = prefix[i - 1] + arr[i];  return prefix; } // Function to return the Count of // the total number of subarrays static int CountSubarray(int []arr, int n) {  int []Prefix = new int[n];  // Calculating the prefix array  Prefix = PrefixSumArray(arr, n);  int last = 0, ans = 0;  Dictionary<int,  int> Hash = new Dictionary<int,  int>();  Hash.Add(0, -1);  for(int i = 0; i <= n; i++)   {   // Check if the element already exists  if (i < n && Hash.ContainsKey(Prefix[i]))  last = Math.Max(last,   Hash[Prefix[i]] + 1);  ans += Math.Max(0, i - last);  // Mark the element  if (i < n)  Hash.Add(Prefix[i], i);  }  // Return the readonly answer  return ans; } // Driver code public static void Main(String[] args) {  int []arr = {1, 3, -2, 4, -1};  int N = arr.Length;  Console.Write(CountSubarray(arr, N)); } } // This code is contributed by shikhasingrajput  

<script> // Javascript program to count the total number of // subarrays for a given array such that its // subarray should have non zero sum // Function to build the Prefix sum array function PrefixSumArray(arr, n) {  let prefix = Array.from({length: n}, (_, i) => 0);    // Store prefix of the first position  prefix[0] = arr[0];    for(let i = 1; i < n; i++)  prefix[i] = prefix[i - 1] + arr[i];    return prefix; }   // Function to return the Count of // the total number of subarrays function CountSubarray(arr, n) {  let Prefix = Array.from({length: n}, (_, i) => 0);    // Calculating the prefix array  Prefix = PrefixSumArray(arr, n);    let last = 0, ans = 0;    let Hash = new Map();    Hash.set(0, -1);    for(let i = 0; i <= n; i++)  {    // Check if the element already exists  if (i < n && Hash.has(Prefix[i]))  last = Math.max(last,  Hash.get(Prefix[i]) + 1);    ans += Math.max(0, i - last);    // Mark the element  if (i < n)  Hash.set(Prefix[i], i);  }    // Return the final answer  return ans; } // Driver code    let arr = [ 1, 3, -2, 4, -1 ];    let N = arr.length;    document.write(CountSubarray(arr, N));    // This code is contributed by code_hunt. </script> 

15

Time Complexity: O(N) 
Auxiliary Space: O(N)