Sub-array with given sum in C
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.
C Code for naive approach
#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
#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
Login/Signup to comment