loremIpsum1771 - 1 month ago 13x

C++ Question

Consider the following problem statement:

Given an unsorted array of integers, find a subarray which adds to a given number. If there are more than one subarrays with sum as the given number, print any of them.

`Examples:`

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33

Ouptut: Sum found between indexes 2 and 4

Input: arr[] = {10, 2, -2, -20, 10}, sum = -10

Ouptut: Sum found between indexes 0 to 3

Input: arr[] = {-10, 0, 2, -2, -20, 10}, sum = 20

Ouptut: No subarray with given sum exists

On this site, the following linear time solution was suggested involving the use of a map to store the sums of the current subsets as the algorithm iterates through the array:

`// Function to print subarray with sum as given sum`

void subArraySum(int arr[], int n, int sum)

{

// create an empty map

unordered_map<int, int> map;

// Maintains sum of elements so far

int curr_sum = 0;

for (int i = 0; i < n; i++)

{

// add current element to curr_sum

curr_sum = curr_sum + arr[i];

// if curr_sum is equal to target sum

// we found a subarray starting from index 0

// and ending at index i

if (curr_sum == sum)

{

cout << "Sum found between indexes "

<< 0 << " to " << i << endl;

return;

}

// If curr_sum - sum already exists in map

// we have found a subarray with target sum

if (map.find(curr_sum - sum) != map.end())

{

cout << "Sum found between indexes "

<< map[curr_sum - sum] + 1

<< " to " << i << endl;

return;

}

map[curr_sum] = i;

}

// If we reach here, then no subarray exists

cout << "No subarray with given sum exists";

}

// Driver program to test above function

int main()

{

int arr[] = {10, 2, -2, -20, 10};

int n = sizeof(arr)/sizeof(arr[0]);

int sum = -10;

subArraySum(arr, n, sum);

return 0;

}

With the test case that is provided in the post, the second if statement checking whether current_sum - sum is never entered. Instead, the sum is found and is printed in the first if statement.

`current_sum-sum`

Answer

```
curr_sum = curr_sum + arr[i];
```

Here:

curr_sum holds the sum of all the entries(up to arr[i]) starting from arr[0]

```
if (curr_sum == sum)
{
cout << "Sum found between indexes "
<< 0 << " to " << i << endl;
return;
}
```

Here:

The if condition checks if the curr_sum is equal to the given sum. Remember, curr_sum holds the sum starting from arr[0].

So, if the indexes for your result subarray is 2 and 4, the above condition is not enough.

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

In that example,

when i = 4, curr_sum would be 38. But if you take 1 and 4 out(arr[0] and arr[1] which is a subarray), you get 33.

```
if (map.find(curr_sum - sum) != map.end())
{
cout << "Sum found between indexes "
<< map[curr_sum - sum] + 1
<< " to " << i << endl;
return;
}
map[curr_sum] = i;
```

The above code does that.

```
map[curr_sum] = i;
```

map stores the index value (i) with the subarray sum ( sum of the arr between indexes 0 and i ) as key. So for the example, it would be:

- map[1]=0
- map[5]=1
- map[25]=2
- map[28]=3
- map[38]=4

This code:

```
map.find(curr_sum - sum)
```

searches the map is if it has an entry with key (curr_sum - sum).

In our example, when i = 4, curr_sum would be 38 and sum as given would be 33. If we eliminate the subarray arr[0,2], we get 33. So, map.find(curr_sum - sum) => map.find(38-33) is a hit since we have entry map[5] = 1.

Hope this clears you

Source (Stackoverflow)

Comments