Print All Subarrays With 0 Sum in Python
All Subarrays with 0 Sum
Here, on this page, we will discuss the program to Print All Subarrays with 0 Sum in Python Programming language.
A simple solution is to consider all subarrays one by one and check if the sum of every subarray is equal to 0 or not. The complexity of this solution would be O(n^2). A better approach is to use Hashing.
Algorithm ( Method 1 )
- Keep the sum of the elements encountered thus far in a variable (say sum).
If the current sum is zero, we discovered a subarray beginning at index 0 and ending at index current index.
- Check to see if the current sum is in the hash table.
- If the current sum already exists in the hash table, it means that it was the sum of some sub-array elements arr…arr[i], and now the same sum is obtained for the current sub-array arr…arr[j], implying that the sum of the sub-array arr[i+1]…arr[j] must be 0.
- Insert the current total into the hash table.
def add(arr, l): for i in range(l - 1): sum = 0 for j in range(i, l): sum += arr[j] if sum == 0: print("Subarray found from Index ", i, "to", j) arr = [6, 3, -1, -3, 4, -2, 2, 4, 6, -12, -7] l = len(arr) add(arr, l)
Subarray found from Index 0 to 10
Subarray found from Index 2 to 4
Subarray found from Index 2 to 6
Subarray found from Index 5 to 6
Subarray found from Index 6 to 9
For similar Questions click on the given button