Program Explanation

The program checks if there exists a subarray within a given array that has a sum equal to zero. It utilizes a hash table to store the cumulative sums and checks if any cumulative sum has been seen before. If it has, a zero sum subarray exists.

Program Structure

1. Import necessary libraries.
2. Define a function to check for the zero sum subarray.
3. Use a hash table (implemented as an array) to keep track of cumulative sums.
4. Iterate through the array while calculating the cumulative sum.
5. Check if the cumulative sum has already been seen.
6. Return true if a zero sum subarray exists, false otherwise.

Code

#include 
#include 
#include 

#define MAX 1000 // Maximum number of elements in the array

// Function to check if there is a subarray with a sum of zero
bool hasZeroSumSubarray(int arr[], int n) {
    // Hash table to store cumulative sums
    bool sumExists[MAX] = {false};
    int sum = 0;

    // Iterate through the array
    for (int i = 0; i < n; i++) {
        // Add current element to sum
        sum += arr[i];

        // Check if sum is zero or already exists in the hash table
        if (sum == 0 || sumExists[sum + MAX]) {
            return true;
        }

        // Mark the sum as existing
        sumExists[sum + MAX] = true;
    }
    return false;
}

// Main function
int main() {
    int arr[MAX], n;

    // Input the number of elements
    printf("Enter the number of elements: ");
    scanf("%d", &n);

    // Input the elements of the array
    printf("Enter the elements:\n");
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    // Check for zero sum subarray
    if (hasZeroSumSubarray(arr, n)) {
        printf("A subarray with sum zero exists.\n");
    } else {
        printf("No subarray with sum zero exists.\n");
    }

    return 0;
}

Documentation

Function: hasZeroSumSubarray

• Parameters:
  • int arr[]: The array of integers.
  • int n: The number of elements in the array.
• Returns: true if a zero sum subarray exists; otherwise, false.

Main Function

• hasZeroSumSubarray to determine if a zero sum subarray exists.

Explanation of the Program:

1. Data Structures: The program uses an array sumExists to keep track of cumulative sums.
2. Logic: It maintains a cumulative sum as it iterates through the input array. If the sum is zero or has been seen before, it concludes that a zero sum subarray exists.
3. User Input: The program takes user input for the number of elements and the elements themselves, making it flexible for different scenarios.