loremIpsum1771 loremIpsum1771 - 2 months ago 7
C++ Question

Finding subarray with given sum

The problem statement is:


Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number.


Examples:

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Ouptut: Sum found between indexes 2 and 4

Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Ouptut: Sum found between indexes 1 and 4

Input: arr[] = {1, 4}, sum = 0
Output: No subarray found


Based on the an explanation of a solution from this post the following solution wouldn't work for negative numbers:

/* An efficient program to print subarray with sum as given sum */
#include<stdio.h>

/* Returns true if the there is a subarray of arr[] with sum equal to 'sum'
otherwise returns false. Also, prints the result */
int subArraySum(int arr[], int n, int sum)
{
/* Initialize curr_sum as value of first element
and starting point as 0 */
int curr_sum = arr[0], start = 0, i;

/* Add elements one by one to curr_sum and if the curr_sum exceeds the
sum, then remove starting element */
for (i = 1; i <= n; i++)
{
// If curr_sum exceeds the sum, then remove the starting elements
while (curr_sum > sum && start < i-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, i-1);
return 1;
}

// Add this element to curr_sum
if (i < n)
curr_sum = curr_sum + arr[i];
}

// If we reach here, then no subarray
printf("No subarray found");
return 0;
}


I tried considering a few different scenarios of inputs but I couldn't think of a case where the input array would contain negative numbers and not yield the correct output. Here is one input array with negative numbers that works:

int arr[] = { 15, 14, -2, 3, -5, 14};


Which input cases is the post referring to when it says that the solution won't work for negative numbers?

Answer

This solution relies on this fact that when we remove an element our sum decreases but having a negative number contradicts with this assumption.

The shortest examples are cases like this -1 5 2 when we are looking for subarrays with sum of 5. The operation will be as follows:

add -1, sum = -1
add 5, sum = 4
add 2, sum = 6
remove -1, sum = 7
remove 5, sum = 2

We have reached the end of the list but we haven't found the desired subarray.

Comments