Check if subarray with 0 sum is exists or not

Given an array of integers, it is often required to check if there exists a subarray with a sum equal to 0. This problem can be solved using two approaches – brute force and hashing.

Approach 1: Brute Force

The brute force approach involves checking every possible subarray in the given array to see if its sum equals 0. This approach has a time complexity of O(n^2) due to the nested loops.

Here is the algorithm in pseudocode:

1. Loop through each element in the array.
2. For each element, loop through the remaining elements in the array to find all possible subarrays.
3. Calculate the sum of each subarray.
4. If the sum of any subarray equals 0, return true.
5. If no subarray is found, return false.

Let’s say we have an array [4, 2, -3, 1, 6] and we want to check if there exists a subarray with a sum equal to 0. Using this algorithm, we would loop through each element and compare it to the remaining elements:

1. Loop through each element in the array: a. Compare 4 to the remaining elements (2, -3, 1, 6). No subarray found. b. Compare 2 to the remaining elements (-3, 1, 6). No subarray found. c. Compare -3 to the remaining elements (1, 6). Found subarray [-3, 1, 6] with sum 4. d. Compare 1 to the remaining elements (6). No subarray found. e. Compare 6 to the remaining element (). No subarray found.
2. Return true.

Approach 2: Hashing

The hashing approach involves storing the cumulative sum of the elements in a hash table. If a cumulative sum repeats itself, it indicates that there is a subarray with a sum of 0. This approach has a time complexity of O(n) due to the constant-time lookup in the hash table.

Here is the algorithm in pseudocode:

1. Create an empty hash table.
2. Initialize the cumulative sum to 0.
3. Loop through each element in the array: a. Add the current element to the cumulative sum. b. Check if the cumulative sum exists in the hash table. c. If the cumulative sum exists, return true. d. If the cumulative sum does not exist, add it to the hash table.
4. If no subarray is found, return false.

Using the same example array [4, 2, -3, 1, 6], we would create a hash table to store the cumulative sums:

1. Create an empty hash table: {}
2. Initialize the cumulative sum to 0.
3. Loop through each element in the array: a. Add the current element to the cumulative sum: i. Add 4 to the cumulative sum: 4 ii. Check if 4 exists in the hash table. No. iii. Add 4 to the hash table: {4: 0} iv. Add 2 to the cumulative sum: 6 v. Check if 6 exists in the hash table. No. vi. Add 6 to the hash table: {4: 0, 6: 1} vii. Add -3 to the cumulative sum: 3 viii. Check if 3 exists in the hash table. No. ix. Add 3 to the hash table: {4: 0, 6: 1, 3: 2} x. Add 1