** please use comments for me to understand it.**** thank you The purpose of thi
ID: 2247360 • Letter: #
Question
** please use comments for me to understand it.**** thank you
The purpose of this exercise is to get familiar with the complexity analysis of algorithms. 1. write a function that gets an array of integers (A) and an integer (k) as its input. 2. write a program to find a contiguous subarray of size k in this array that sums up to zero. 3. If A = [1, 2, -3, -4, 5, 6] and k = 4, this subarray is [2, -3, -4, 5]. 4. time complexity of your program at its worst-case should be O(N), where N is the size of array.Explanation / Answer
// c++ code
// Input to the function - array, array_size, k(size of subarray)
// this function returns the minimum possible index of subarray of length k, whose sum of elements is zero.
// if no such subarray exist it returns -1
/* This code will also work for c , if we exchange size of sum array to some constant value, because we can't
declare variable size array in c */
/* complexity of this program is O(N) as it traverses array of size N for two times only */
int subarray_index(int arr[], int N, int k)
{
int i = 0;
int sum[N+1];
sum[0] = 0;
for(i=1; i<=N; i++)
sum[i] = sum[i] + arr[i-1];
for(i=0;i<=N-k;i++)
{
if(sum[i+k] - sum[i] == 0)
return i;
}
return -1;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.