Introduction

This program finds a contiguous subarray within a one-dimensional array of integers that sums to a given value. The solution utilizes hashing for efficient lookup and storage, allowing us to achieve an average time complexity of O(n).

Program Structure

• Header Files: We include standard libraries for input/output and for using the hash table.
• Function Definitions: We define the main function and a helper function to find the subarray with the given sum.
• Main Logic: The main function takes user input for the array and the target sum, then calls the helper function to check for the subarray.

C Program

#include 
#include 
#include 

// Structure for the hash table
typedef struct {
    int *keys;   // Store keys (cumulative sums)
    int *values; // Store indices of the keys
    int size;    // Current size of the hash table
    int capacity; // Maximum capacity of the hash table
} HashTable;

// Function to create a hash table
HashTable* createHashTable(int capacity) {
    HashTable *table = (HashTable*)malloc(sizeof(HashTable));
    table->capacity = capacity;
    table->size = 0;
    table->keys = (int*)malloc(capacity * sizeof(int));
    table->values = (int*)malloc(capacity * sizeof(int));
    return table;
}

// Hash function to map values to key
int hashFunction(int key, int capacity) {
    return key % capacity;
}

// Function to insert key-value pair in the hash table
void insert(HashTable *table, int key, int value) {
    int index = hashFunction(key, table->capacity);
    while (table->keys[index] != 0) {
        index = (index + 1) % table->capacity; // Linear probing
    }
    table->keys[index] = key;
    table->values[index] = value;
    table->size++;
}

// Function to search for a key in the hash table
int search(HashTable *table, int key) {
    int index = hashFunction(key, table->capacity);
    while (table->keys[index] != 0) {
        if (table->keys[index] == key) {
            return table->values[index];
        }
        index = (index + 1) % table->capacity; // Linear probing
    }
    return -1; // Not found
}

// Function to find the subarray with the given sum
void findSubarrayWithSum(int arr[], int n, int sum) {
    HashTable *table = createHashTable(n);
    int cumulativeSum = 0;

    for (int i = 0; i < n; i++) { cumulativeSum += arr[i]; // Check if cumulative sum equals target sum if (cumulativeSum == sum) { printf("Subarray found from index 0 to %d\n", i); return; } // Check if there is a subarray with sum equal to cumulativeSum - sum int index = search(table, cumulativeSum - sum); if (index != -1) { printf("Subarray found from index %d to %d\n", index + 1, i); return; } // Insert cumulativeSum into the hash table insert(table, cumulativeSum, i); } printf("No subarray found with the given sum.\n"); free(table->keys);
    free(table->values);
    free(table);
}

// Main function
int main() {
    int n, sum;
    printf("Enter number of elements in array: ");
    scanf("%d", &n);
    int *arr = (int*)malloc(n * sizeof(int));

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

    printf("Enter the sum to find: ");
    scanf("%d", &sum);

    findSubarrayWithSum(arr, n, sum);

    free(arr);
    return 0;
}

How It Works

The program follows these key steps:

1. It defines a hash table structure to store cumulative sums and their respective indices.
2. As we iterate through the array, we maintain a cumulative sum.
3. For each cumulative sum, we check:
   • If it equals the target sum, we have found a subarray from the start to the current index.
   • If the difference between the cumulative sum and the target sum exists in the hash table, we retrieve the index and identify the subarray.
4. If no such subarray is found after processing the entire array, a message is displayed.

Conclusion

This C program effectively utilizes hashing to find a subarray with a specified sum, achieving an average time complexity of O(n). This method is efficient and scalable for larger datasets.