Subarray with Given Sum in C

This document explains how to find a subarray with a given sum in an array using C. The solution provided is based on the sliding window approach.

Problem Statement

Given an array of integers and a target sum, find a continuous subarray that adds up to the target sum. If such a subarray exists, return the starting and ending indices of the subarray. If no such subarray exists, return -1 for both indices.

Approach

The approach used here is the sliding window technique. The idea is to use two pointers (start and end) to maintain a window that contains the current subarray being checked. If the sum of the current window is less than the target sum, expand the window by moving the end pointer to the right. If the sum is greater than the target, shrink the window by moving the start pointer to the right. This way, we efficiently find the subarray with the given sum.

C Program

#include <stdio.h>

/**
 * Finds the subarray with a given sum.
 *
 * @param arr The input array of integers.
 * @param n The size of the array.
 * @param targetSum The target sum to find in the subarray.
 * @param start A pointer to store the starting index of the subarray.
 * @param end A pointer to store the ending index of the subarray.
 * @return 1 if the subarray is found, 0 otherwise.
 */
int findSubarrayWithSum(int arr[], int n, int targetSum, int *start, int *end) {
    int currentSum = 0;
    *start = 0;
    *end = 0;

    for (int i = 0; i < n; i++) { currentSum += arr[i]; while (currentSum > targetSum && *start <= i) {
            currentSum -= arr[*start];
            (*start)++;
        }

        if (currentSum == targetSum) {
            *end = i;
            return 1;
        }
    }

    return 0;
}

/**
 * Main method to test the findSubarrayWithSum function.
 *
 * @return 0 on successful execution.
 */
int main() {
    int arr[] = {1, 2, 3, 7, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int targetSum = 12;
    int start, end;

    if (findSubarrayWithSum(arr, n, targetSum, &start, &end)) {
        printf("Subarray with given sum found from index %d to %d\n", start, end);
    } else {
        printf("No subarray with the given sum found.\n");
    }

    return 0;
}
    

Explanation

The program consists of two main parts: the findSubarrayWithSum function and the main function.

findSubarrayWithSum Function

This function takes four parameters: an array of integers, the size of the array, the target sum, and pointers to store the starting and ending indices of the subarray. It uses the sliding window approach to find the subarray that sums to the target. It maintains a window defined by two pointers, start and end. It expands the window by moving through the array and shrinks it as needed. If it finds a window whose sum equals the target, it returns 1 and sets the starting and ending indices. If no such subarray is found, it returns 0.

main Function

This function is used to test the findSubarrayWithSum function. It creates an array and a target sum, calls the function with these values, and prints the result.

How to Run the Program

1. Copy the C code into a file named subarray_with_given_sum.c.
2. Open a terminal or command prompt and navigate to the directory containing the file.
3. Compile the program using the command: gcc subarray_with_given_sum.c -o subarray_with_given_sum
4. Run the program using the command: ./subarray_with_given_sum

If the subarray with the given sum is found, the program will print the starting and ending indices. Otherwise, it will indicate that no such subarray exists.