Count Of Subarrays Having Sum Equals To K

faq

1. Why is the space complexity O(n)?
The space complexity of the above code is also O(N) as we are storing the sum and frequency at every array index in the hashmap.

2.  Why is the time complexity O(n)?
The time complexity of the above code is O(N) where N is the number of elements in the array as we are traversing the array and calculating the prefix sum to find the number of subarrays with sum K.

3. Why is the number of subarrays of an array given by (n * (n + 1)) / 2?
 The number of subarrays of an array can be calculated as there are,

1 subarray of length n
2 subarrays of length n – 1
……
n subarrays of length 1
So, the total number of subarrays count out to a total of 1 + 2 + 3 + … n = (n * (n + 1)) / 2.

4. What does the term "Count of Subarrays Having Sum equal to K" mean?
Ans -> we have to count all the subarrays in for the given array whose sum is equal to K and we need to return its count.

5. How can we use HashMap into this question?
Ans-> We will make a hashmap of type integer-integer and it is going to store the frequency of the sum that we get at every index. 

hints

1.Will Brute force work here? Try to optimize it.
2.Can we optimize it by using some extra space?
3.What about storing sum frequencies in a hash table? Will it be useful?
4.sum(i,j)=sum(0,j)-sum(0,i), where sum(i,j) represents the sum of all the elements from index i to j-1. Can we use this property to optimize it.

mcq

1.  If the value of current sum is ________ the desired sum at any instance increment count of subarrays by one.
a. equal to
b. greater than
c. less than
d. none of the above

Ans: a. equal to

2.  What is the average time complexity of this problem?
a) O(n*n)
b) O(n)
c) O(1)
d) None of the above
Ans: b

3. What is the average space complexity of this problem?
a) O(n*n)
b) O(1)
c) O(n)
d) None of the above
Ans: c


4. What is the Subarray?
a. A subarray is a Subsequence of array.
b. A subarray is a contiguous part of array.
c. Both of the above
d. None of the above

Ans -> b. A subarray is a contiguous part of array.

5. What are the Subarrays of arr = [1,2,3]?
a. [1],[1,2],[1,2,3]
b. [1],[1,2],[1,2,3],[2],[2,3],[3]
c. [1],[1,2],[1,3],[1,2,3],[2],[2,3],[3]
d. None of the above

Ans -> b. [1],[1,2],[1,2,3],[2],[2,3],[3]