0 like 0 dislike
779 views
N is the length of array .

1<=N<=1000000

-100000<=A[i]<=100000

Explaining algorithm is mandatory. Only giving code and no explanation is not allowed. Also add your name at the bottom of answer so you get the due credits. Direct libraries in python are not allowed to be used as they skip the lagorithm parts sometimes.

Example Array : 4 -8 7 8 -100 15

k=15

Output : {7,8} is the largesr subarray with sum =15
| 779 views

0 like 0 dislike
```//Time = O(n)
//space = O(n)
//we will store the prefix sum as key, and the index as value in a map(index denotes the prefix sum till that point
//we will iterate the array,calculate the prefix sum till that point, if (prefixsum-k) is present in the map, then find the index of prefixsum-k, subtract the current counter and find the maximim length
```
```
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,sum=0,k,x,j;
cin>>n>>k;
vector<int> a(n);
map<int,int> mp;

for(int i=0;i<n;i++)
{
cin>>a[i];

}
int mx=INT_MIN;
mp[0]=0;
for(int i=0;i<n;i++)
{

sum+=a[i];
if(mp.find(sum-k)!=mp.end())
{
j=mp[sum-k];
mx=max(mx,i-j);
}
mp[sum]=i+1;
}
if(mx<n)
cout<<++mx;
else
cout<<" no subarray where sum= k";
}```
by
edited by anonymous
0 like 0 dislike
```l=[1,5,6,7,8]   #l=list(map(int,input().split())) or l=[int(x) for x in input().split()]
k=11            #k=input()
le,c=0,0        #le for calculating length of the array,
for i in l:
le+=1
for i in range(len(l)):    #i as starting index and j as ending index
for j in range(i+1,len(l)+1):
s=0
for i in range(i,j):
#print(i,j)
s+=l[i]
#print('s =',s)
if s==k:
c+=1
print(c)```

Time Complexity : O(N^2)

by
0 0
Your approach is not efficient . It uses 2 nested-for loops , hence the time complexity will be O(n*n) .