loremIpsum1771 - 7 months ago 35

C++ Question

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};`

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.