fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4.  
  5.  
  6. int smallestSubarray(vector<int>arr,int k)
  7.  {
  8.  	unordered_map<int,int>mp;
  9.  	mp[0]=-1;
  10.     int prefixsum=0;
  11.     int n=arr.size();
  12.     int  length=INT_MAX;
  13.     for(int i=0;i<n;i++)
  14.      {
  15.      	prefixsum=prefixsum+arr[i];
  16.      	if(mp.find(prefixsum-k)!=mp.end())
  17.      	 {
  18.      	 	int current_len=i-mp[prefixsum-k];
  19.      	 	length=min(current_len,length);
  20.      	 }
  21.      	 mp[prefixsum]=i;
  22.      }
  23.      return length;
  24.  }
  25.  
  26.  
  27. int longestSubarray(vector<int>arr,int k)
  28.  {
  29.  	unordered_map<int,int>map;
  30.  	map[0]=-1;
  31.     int prefixsum=0;
  32.     int n=arr.size();
  33.     int  length=INT_MIN;
  34.     for(int i=0;i<n;i++)
  35.      {
  36.      	prefixsum=prefixsum+arr[i];
  37.      	if(map.find(prefixsum-k)!=map.end())
  38.      	 {
  39.      	 	int current_len=i-map[prefixsum-k];
  40.      	 	length=max(current_len,length);
  41.      	 }
  42.      	 if(map.find(prefixsum)==map.end())
  43.      	     {
  44.      	     	map[prefixsum]=i;
  45.      	     }
  46.      } 	     
  47.      return length;
  48.  }
  49.  
  50. int countShortestSubarray(vector<int>arr,int k,int target)
  51. {
  52. 	unordered_map<int,int>mp;
  53.  	mp[0]=-1;
  54.     int prefixsum=0;
  55.     int n=arr.size();
  56.     int count=0;
  57.     int length,current_length;
  58.     for(int i=0;i<n;i++)
  59.      {
  60.      	prefixsum=prefixsum+arr[i];
  61.      	if(mp.find(prefixsum-k)!=mp.end())
  62.      	 {
  63.      	    current_length = i-mp[prefixsum-k];
  64.      	    if(current_length==target)
  65.      	     count++;
  66.      	 }
  67.  
  68.      	 mp[prefixsum]=i;
  69.      }
  70.      return count;
  71. }
  72.  
  73. int countLongestSubarray(vector<int>arr,int k,int target)
  74. {
  75. 	unordered_map<int,int>mp;
  76.  	mp[0]=-1;
  77.     int prefixsum=0;
  78.     int n=arr.size();
  79.     int count=0;
  80.     int length,current_length;
  81.     for(int i=0;i<n;i++)
  82.      {
  83.      	prefixsum=prefixsum+arr[i];
  84.      	if(mp.find(prefixsum-k)!=mp.end())
  85.      	 {
  86.      	    current_length = i-mp[prefixsum-k];
  87.      	    if(current_length==target)
  88.      	     count++;
  89.      	 }
  90.      	 if(mp.find(prefixsum)==mp.end())
  91.      	 mp[prefixsum]=i;
  92.      }
  93.      return count;
  94. }
  95.  
  96.  
  97. int main() {
  98.    vector<int>arr={2,6,4,4,0,1,6,1};
  99. 	int k;
  100. 	cin>>k;
  101.  
  102. 	int smallest_length = smallestSubarray(arr,k);
  103. 	int largest_length = longestSubarray(arr,k);
  104.  
  105.   cout<<smallest_length<<endl;
  106.   cout<<largest_length<<endl;
  107.  
  108. 	cout<<countShortestSubarray(arr,k,smallest_length);
  109. 	cout<<endl;
  110. 	cout<<countLongestSubarray(arr,k,largest_length);
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117. 	// cout<<smallestSubarray(arr,k);
  118.  //   cout<<endl;
  119.  //   cout<<longestSubarray(arr,k);
  120.  
  121.  
  122.  
  123.  
  124. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
8
stdout
copy 
2
4
2
1
https://ideone.com/JLUhtr
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!