Find a subarray with a given sum.
Find a subarray with a given sum.
The simple solution is to recognize all subarrays one by one and to check each subarray's sum. The quick solution follows the following program.
Algorithm:
- From beginning to end, traverse the array.
- For each index in the internal loop update number = sum + array[s]
- If the sum is equal to the sum given, then the subarray is printed out.
/* A simple program to print
subarray with sum as given sum */
#include <stdio.h>
int subArraySum(int arr[], int p, int sum)
{
int curr_sum, k, s;
// Pick a starting point
for (k = 0; k < p; k++) {
curr_sum = arr[k];
// try all subarrays starting with 's'
for (s = k + 1; s <= p; s++) {
if (curr_sum == sum) {
printf(
"Sum found between indexes %d and %d",
k, s - 1);
return 1;
}
if (curr_sum > sum || s == p)
break;
curr_sum = curr_sum + arr[s];
}
}
printf("No subarray found");
return 0;
}
// Driver program to test above function
int main()
{
int arr[] = { 15, 4, 8, 16, 18, 10, 20, 43 };
int p = sizeof(arr) / sizeof(arr[0]);
int sum = 43;
subArraySum(arr, p, sum);
return 0;
}
Output:
Effective approach: If all of the elements in the collection are positive, then there is a concept. There is no probability that adding elements to the current subarray would be x (given sum) if a subarray has a number greater than the given sum. The aim is to use an approach similar to a sliding window. Start by adding elements to the subarray with an empty subarray until the sum is less than x. If the sum is higher than x, delete elements from the current subarray startup.
Algorithm:
Construct three variables, s=0, sum = 0
From beginning to end traverse the array.
Change the variable sum by adding current element, sum = sum + array[s]
Change the value of the variable as value = sum-array[s], and update s as, s++ if the sum is larger than the sum.
/* An efficient program to print
subarray with sum as given sum */
#include <stdio.h>
int subArraySum(int arr[], int t, int sum)
{
/* Initialize curr_sum as
value of first element and
starting point as 0 */
int curr_sum = arr[0], start = 0, m;
/* Add elements one by one to
curr_sum and if the curr_sum
exceeds the sum, then remove
starting element */
for (m = 1; m <= t; m++) {
// If curr_sum exceeds the sum,
// then remove the starting elements
while (curr_sum > sum && start < m - 1) {
curr_sum = curr_sum - arr[start];
start++;
}
// If curr_sum becomes equal to sum,
// then return true
if (curr_sum == sum) {
printf(
"Sum found between indexes %d and %d",
start, m - 1);
return 1;
}
// Add this element to curr_sum
if (m < t)
curr_sum = curr_sum + arr[m];
}
// If we reach here, then no subarray
printf("No subarray found");
return 0;
}
// Driver program to test above function
int main()
{
int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
int t = sizeof(arr) / sizeof(arr[0]);
int sum = 23;
subArraySum(arr, t, sum);
return 0;
}
Output:
