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!