Sub-array with given sum in C

April 13, 2023

Sub-array with given sum

Here, in this page we will write the program for sub-array with given sum in C.Given an Array of non negative Integers and a number. You need to print all the starting and ending indices of Sub-arrays having their sum equal to the given integer.
Example : arr[ ] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Output : Sum found between indexes 1 and 4 Sum of elements between indices 1 and 4 is (4 + 0 + 0 + 3) = 7

Sub-Array With Given Sum in C

A Sub-array with given sum code in C is a program that takes an array of integers and a target sum as input, and finds a contiguous subarray within the array that adds up to the target sum. The program then outputs the starting and ending indices of the subarray, or indicates if no such subarray exists.

On this page we will discuss two different methods for this-

Naive Approach
Sliding Window Approach

Naive approach: Naive approach uses a nested loop to check all possible subarrays of the given array. For each starting index i, it checks all subarrays starting from i and ending at j, and calculates their sum. If the sum is equal to the given sum, it prints the indices of the subarray and returns. If no subarray is found, it prints a message indicating that no subarray was found.

Algorithm:

Step 1: Take the input array and target sum as input.
Step 2: Traverse the array from the first element to the last element.
Step 3: For each element i, initialize the current sum as arr[i].
Step 4: Traverse the array from i+1 to n, where n is the length of the array.
Step 5: For each element j, add arr[j] to the current sum.
Step 6: If the current sum is equal to the target sum, print the starting and ending indices of the subarray and return.
Step 7: If the current sum is greater than the target sum or j is equal to n, break out of the loop and continue with the next element i.
Step 8: If no subarray is found, print a message indicating that no subarray was found.

Size of sub-array with max sum

Largest Sum Contigous SubArray

Triplet that sum to a given value

Segregate 0’s 1’s and 2’s in array

Sort elements in array by frequency

C Code for naive approach

Run

#include <stdio.h>

void findSubarray(int arr[], int n, int sum)
{
    for (int i = 0; i < n; i++) {
        int curr_sum = 0;

        for (int j = i; j < n; j++) {
            curr_sum += arr[j];

            if (curr_sum == sum) {
                printf("Subarray found between indexes %d and %d\n", i, j);
                return;
            }
        }
    }

    printf("No subarray found\n");
}

int main()
{
    int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 23;

    findSubarray(arr, n, sum);

    return 0;
}

Output

Subarray found between indexes 1 and 4

Sliding Window approach:It uses a sliding window approach, where a window of elements is moved from left to right to find the sum. The start and end of the window are stored as variables and updated as necessary. If a subarray with the sum is found, its indices are printed to the console. Otherwise, a message indicating that no subarray was found is printed.

Algorithm:

Step 1: Take the input array and target sum as input.
Step 2: Initialize two variables, start and curr_sum, to the first element of the array.
Step 3: Traverse the array from the second element to the last element.
Step 4: If the current sum is greater than the target sum, increment start and subtract arr[start-1] from curr_sum until curr_sum is less than or equal to the target sum.
Step 5: If the current sum is equal to the target sum, print the starting and ending indices of the subarray and return.
Step 6: If the current sum is less than the target sum and i is less than n, add arr[i] to curr_sum and continue with the next element i.
Step 7: If no subarray is found, print a message indicating that no subarray was found.

C Code for sliding window approach

Run

#include <stdio.h>

void findSubarray(int arr[], int n, int sum)
{
    int curr_sum = arr[0];
    int start = 0;

    for (int i = 1; i <= n; i++) { while (curr_sum > sum && start < i - 1) {
            curr_sum = curr_sum - arr[start];
            start++;
        }

        if (curr_sum == sum) {
            printf("Subarray found between indexes %d and %d\n", start, i - 1);
            return;
        }

        if (i < n)
            curr_sum = curr_sum + arr[i];
    }

    printf("No subarray found\n");
}

int main()
{
    int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 23;

    findSubarray(arr, n, sum);

    return 0;
}

Output

Subarray found between indexes 1 and 4

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Arrays

Introduction to Arrays – C | C++ | Java
Introduction to 2-D Arrays – C | C++ | Java
Sorting of Array – C | C++ | Java
Array Rotation – C | C++ | Java
Reverse an array or string- C | C++ | Java
Find pairs in array with given sum – C | C++ | Java
Sort the array in Waveform – C | C++ | Java
Majority Element in Array – C | C++ | Java
Boyer-Moore’s Voting Algorithm – C | C++ | Java
K-pairs with smallest sum in 2 arrays – C | C++ | Java
Largest Sum Contigous SubArray – C | C++ | Java
Maximum Average Sub-array of K length – C | C++ | Java
Size of sub-array with max sum – C | C++ | Java
Sub-array with given sum – C | C++ | Java
Triplet that sum to a given value – C | C++ | Java
Segregate 0’s and 1’s in array – C | C++ | Java
Segregate 0’s 1’s and 2’s in array – C | C++ | Java
Sort elements in array by frequency – C | C++ | Java
Finding pythagorean triplets in an array – C | C++ | Java
Reorder array using given indexes – C | C++ | Java
Merging two sorted arrays – C | C++ | Java
Minimum number of Merge Operations to make an Array Palindrome – C | C++ | Java
Find Zeros to be Flipped so that number of Consecutive 1’s is maximized – C | C++ | Java