Skip to content
Advertisement

Stuck in this question and couldn’t understand the code for the sum of subarray

I am stuck in the end function part of the question and arr[start]/arr[end] as well I fail to understand the code. The question is as follows:

Given an unsorted array A of size N that contains only non-negative integers, find a continuous sub-array which adds to a given number S.

You don’t need to read input or print anything. The task is to complete the function subarraySum() which takes arr, N and S as input parameters and returns a list containing the starting and ending positions of the first such occurring subarray from the left where sum equals to S. The two indexes in the list should be according to 1-based indexing. If no such subarray is found, return -1.

def subArraySum(arr,n,sum):
    curr_sum = 0 
    start = 0
    end=0
    i = 0
    
    while end <= n-1:
        if curr_sum<sum:
            curr_sum=curr_sum+arr[end]
            end=end+1
        while curr_sum>sum:
            curr_sum=curr_sum-arr[start]
            start=start+1
        if curr_sum==sum:
            break
    if curr_sum != sum:
        return[-1]
    else:
        return start+1, end

Advertisement

Answer

This code is looking for the earliest contiguous sequence that adds up to a given number. For example:

1  1  2  4  5  2

Is a sequence of 6 numbers. If we are looking for the first sequence that adds to 7, we would end up with 1, 2, and 4, in a subsequence defined by two indices, start and end:

start|
  1  1  2  4  5  2
           end|

Note that end is one past the end. This is a common convention. Also any given time, curr_sum is the sum of all the numbers in the subsequence. In the abovecase, 7.

The code starts with start and end at 0. As the code loops, if the total of the current subsequence, curr_sum, is less than the desired sum, it makes the subsequence longer from front end by moving the end up one. If the curr_sum is too big, it makes the subsequence shorter by moving the start up as many times as needed. If curr_sum is the right sum, then it breaks out of function and returns the start and end indices.

All this said, there’s different ways you could track the indices here. Best I can manage, the subsequence is defined by 0-based indices from start, up to, but not including, end. And then at the end, it returns 1-based indices that include the end index, which is why it’s using start+1, end instead of start, end.

User contributions licensed under: CC BY-SA
7 People found this is helpful
Advertisement