Discuss Subarray with zero sum and given sum?

Software Development
#1

A subarray is a contiguous part of an array. An array that is inside another array

Problem Statement:

Given an array of positive and negative numbers, find if there is a subarray (of size at least one) with 0 sums.

Example:

Input: {4, 2, -3, 1, 6}
Output: true
Explanation: There is a subarray with zero-sum from index 1 to 3.

we are using the following approach:

  • Traverse the array from start to end.
  • From every index start another loop from i to the end of the array to get all subarrays starting from i, and keep a variable currentSum to calculate the sum of every subarray.
  • For every index in inner loop update currentSum = currentSum + arr[j]
  • If the currentSum is equal to the given sum then print the subarray.

Code:

bool hasZeroSumSubarray(int nums[], int n)
{
    unordered_set<int> set;
    set.insert(0);
    int sum = 0;


    for (int i = 0; i < n; i++)
    {
        sum += nums[i];
        if (set.find(sum) != set.end()) 
            return true;
        else 
            set.insert(sum);
    }
    return false;
}

Subarray with Given Sum

Problem Statement:

Given an array arr[] of non-negative integers and an integer sum, find a continuous subarray that adds to a given sum.

Note: There may be more than one subarray with sum as the given sum, print first such subarray.

Examples:

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Output: Sum found between indexes 2 and 4
Explanation: Sum of elements between indices 2 and 4 is 20 + 3 + 10 = 33

Code:


bool find_Subarray(int arr[], int N, int required) {
  int sum = 0;
  for (int i = 0; i < N; i++) {
    sum = arr[i];
    for (int j = i + 1; j < N + 1; j++) {
      if (sum == required) {
        // found subarray with given sum
        return true;
      } else if (sum > required) {
        break;
      }
      sum = sum + arr[j];
    }
  }
  return false;
}