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
.