Given an array arr[] of N integers such that no element is 0 in that array, the task is to find the minimum number of elements to be inserted such that no subarray of the new array has sum 0.
Examples:
Input: N = 3, arr[] = {1, -1, 1}
Output: 2
Explanation: As in the array the sum of first two element is 0 that is 1+(-1) = Â 0.Â
To avoid this, insert an element. Insert 10 at position 2.Â
The array become {1, 10, -1, 1}.Â
Now the sum of last 2 element is 0. To avoid this insert an element.Â
Insert 10 at position 4. Array become {1, 10, -1, 10, 1}.Â
Now, no subarray have sum 0.Â
So we have to insert minimum 2 integers in the array.Input: N = 4, arr[] = {-2, 1, 2, 3}
Output:Â
Explanation: No array is there whose sum is 0.Â
So no need to insert element.
Approach: The problem can be solved based on the following observation.
Observations:
- If we get any subarray with sum 0. Then insert an element just 1 place before the position where you got sum 0. So that sum will not remain 0 and start doing sum again.
- Do the same process till the end and print how many times you have inserted element.
Follow the steps to solve the problem:
- Take an unordered_map to store the sum detail to know if there is a subarray with sum 0.
- Take a variable ans and initialize it to 0 to store the minimum number of elements to be inserted.
- Traverse the array and add every element into the array and also note the sum detail in the map.
- If, you got sum 0 (which can be found by checking if the sum is already present in the map):Â
- Then increase the ans by 1 and change the sum to the current element value because you have taken care of the previous elements and also remove the entries of the sum from the map.
- Repeat this step whenever there is a subarray with sum 0.
- In last return ans.
Below is the implementation for the above approach.
C++
// C++ code for the above approach:Â
#include <bits/stdc++.h>using namespace std;Â
// Function to find the minimum count// of required insertionsint getElements(int N, int arr[]){    // To store the previous sums    unordered_map<long long int, int> forSum;Â
    // Final answer    int ans = 0;Â
    // To store current sum    long long int sum = 0;Â
    // Traversing array    for (int i = 0; i < N; i++) {Â
        // Adding elements        sum += arr[i];Â
        // Storing occurrence        forSum[sum]++;Â
        // If found any subarray with sum 0        if (sum == 0 || forSum[sum] > 1) {            ans++;Â
            // New sum            sum = arr[i];Â
            // Clearing previous data            forSum.clear();Â
            // Storing new sum            forSum[sum]++;        }    }    return ans;}Â
// Driver codeint main(){Â Â Â Â int N = 3;Â Â Â Â int arr[] = { 1, -1, 1 };Â
    // Function call    cout << getElements(N, arr) << endl;    return 0;} |
Java
// Java code for the above approach:import java.io.*;import java.util.*;Â
class GFG{Â
  // Function to find the minimum count  // of required insertions  public static int getElements(int N, int arr[])  {Â
    // To store the previous sums    HashMap<Integer, Integer> forSum      = new HashMap<Integer, Integer>();    // Final answer    int ans = 0;Â
    // To store current sum    int sum = 0;Â
    // Traversing array    for (int i = 0; i < N; i++) {Â
      // Adding elements      sum += arr[i];Â
      // Storing occurrence      if (forSum.get(sum) != null)        forSum.put(sum, forSum.get(sum) + 1);      else        forSum.put(sum, 1);Â
      // If found any subarray with sum 0      if (sum == 0          || (forSum.get(sum) != null              && forSum.get(sum) > 1)) {        ans++;Â
        // New sum        sum = arr[i];Â
        // Clearing previous data        forSum.clear();Â
        // Storing new sum        forSum.put(sum, 1);      }    }    return ans;  }Â
  // Driver Code  public static void main(String[] args)  {    int N = 3;    int arr[] = { 1, -1, 1 };Â
    // Function call    System.out.print(getElements(N, arr));  }}Â
// This code is contributed by Rohit Pradhan |
Python3
# Python code for the above approachÂ
# Function to find the minimum count# of required insertionsdef getElements(N, arr):       # To store the previous sums    forSum = {}Â
    # Final answer    ans = 0;Â
    # To store current sum    sum = 0;Â
    # Traversing array    for i in range(N):Â
        # Adding elements        sum += arr[i];Â
        # Storing occurrence        if(sum in forSum):            forSum[sum] += 1        else:            forSum[sum] = 1Â
        # If found any subarray with sum 0        if (sum == 0 or forSum[sum] > 1):            ans += 1Â
            # New sum            sum = arr[i];Â
            # Clearing previous data            forSum.clear();Â
            # Storing new sum            if(sum in forSum):                forSum[sum] += 1            else:                forSum[sum] = 1Â
    return ans;Â
# Driver CodeN = 3;arr = [ 1, -1, 1 ];Â
# Function callprint(getElements(N, arr));Â Â Â Â Â Â Â Â Â # This code is contributed by Saurabh Jaiswal |
C#
// C# implementation of above approachusing System;using System.Collections.Generic;Â
class GFG {Â
  // Function to find the minimum count  // of required insertions  static int getElements(int N, int[] arr)  {Â
    // To store the previous sums    Dictionary<int,    int> forSum = new Dictionary<int,int>();Â
    // Final answer    int ans = 0;Â
    // To store current sum    int sum = 0;Â
    // Traversing array    for (int i = 0; i < N; i++) {Â
      // Adding elements      sum += arr[i];Â
      // Storing occurrence      forSum.Add(sum, 1);Â
      // If found any subarray with sum 0      if (sum == 0 || forSum[sum] > 1) {        ans++;Â
        // New sum        sum = arr[i];Â
        // Clearing previous data        forSum.Clear();Â
        // Storing new sum        forSum.Add(sum, 1);      }    }    return ans;  }Â
  // Driver Code  public static void Main()  {    int N = 3;    int[] arr = { 1, -1, 1 };Â
    // Function call    Console.Write(getElements(N, arr));  }}Â
// This code is contributed by code_hunt. |
Javascript
<script>Â Â Â Â Â Â Â Â // JavaScript code for the above approachÂ
// Function to find the minimum count// of required insertionsfunction getElements(N, arr){    // To store the previous sums    var forSum = new Map();   //let forSum= new Array();Â
    // Final answer    let ans = 0;Â
    // To store current sum    let sum = 0;Â
    // Traversing array    for (let i = 0; i < N; i++) {Â
        // Adding elements        sum += arr[i];Â
        // Storing occurrence        forSum[sum]++;Â
        // If found any subarray with sum 0        if (sum == 0 || forSum[sum] > 1) {            ans++;Â
            // New sum            sum = arr[i];Â
            // Clearing previous data            forSum.clear();Â
            // Storing new sum            forSum[sum]++;        }    }    return ans;}Â
        // Driver CodeÂ
    let N = 3;    let arr = [ 1, -1, 1 ];Â
    // Function call    document.write(getElements(N, arr));                 // This code is contributed by sanjoy_62.    </script> |
Output
2
Time Complexity: O(N) because the array is traversed only once and at most N elements are cleared from the map.
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!
