Subarray_Concept

#include<bits/stdc++.h>
using namespace std;

bool check_subarray_0sum(vector<int> &v, int n) {
	map<int, int> m;
	int curr_sum = 0;
	for (int i = 0; i < n; i++) {
		curr_sum += v[i];
		if (m.find(curr_sum) != m.end()) return true;
		m[curr_sum] = 1;//marked the cur_sum
	}
	return false;
}

int count_subarrays_0sum(vector<int>& v, int n) {
	map<int, int> m;
	int curr_sum = 0, countans = 0;
	m[0]++;
	for (int i = 0; i < n; i++) {
		curr_sum += v[i];
		if (m.find(curr_sum) != m.end()) {
			countans += m[curr_sum];
		}
		m[curr_sum]++;//marked the cur_sum
	}
	return countans;
}


int maxlength_subarray_0sum(vector<int> &v, int n) {
	map<int, int> m;
	int curr_sum = 0, maxlen = 0;
	m[0] = -1;
	for (int i = 0; i < n; i++) {
		curr_sum += v[i];
		if (m.find(curr_sum) != m.end()) {
			maxlen = max(maxlen, (i - m[curr_sum]));
		}
		else {
			m[curr_sum] = i;
		}
	}
	return maxlen;
}




bool check_subarray_ksum(vector<int> &v, int n, int k) {
	map<int, int> m;
	int curr_sum = 0;
	for (int i = 0; i < n; i++) {
		curr_sum += v[i];
		if (m.find(curr_sum - k) != m.end()) return true;
		m[curr_sum] = 1;//marked the cur_sum
	}
	return false;
}

int count_subarrays_ksum(vector<int>& v, int n, int k) {
	map<int, int> m;
	int curr_sum = 0, countans = 0;
	m[0]++;
	for (int i = 0; i < n; i++) {
		curr_sum += v[i];
		if (m.find(curr_sum - k) != m.end()) {
			countans += m[curr_sum - k];
		}
		m[curr_sum]++;//marked the cur_sum
	}
	return countans;
}


int maxlength_subarray_ksum(vector<int> &v, int n, int k) {
	map<int, int> m;
	int curr_sum = 0, maxlen = 0;
	m[0] = -1;
	for (int i = 0; i < n; i++) {
		curr_sum += v[i];
		if (m.find(curr_sum - k) != m.end()) {
			maxlen = max(maxlen, (i - m[curr_sum - k]));
		}
		else {
			m[curr_sum] = i;
		}
	}
	return maxlen;
}



int main() {

	/*
	given an array of length n, a[n];
	n<=10^5, a[i]<=10^9
	1.> check whether a subarray with sum 0 present or not
	2.> count number of subarrays with sum 0.
	3.> find max length of subarray with 0 sum.
	*/

	int n, k; cin >> n >> k;
	vector<int> v(n);
	for (int i = 0; i < n; i++) cin >> v[i];

	cout << check_subarray_0sum(v, n) << " " << endl;//present ->1, not present ->0
	//true -> 1, false -> 0

	cout << "count of subarrays with 0sum -> " << count_subarrays_0sum(v, n) << " " << endl;

	cout << "max length of subarray with 0 sum -> " << maxlength_subarray_0sum(v, n) << " " << endl;


	/*
		given an array of length n,k, a[n];
		n<=10^5, a[i]<=10^9
		1.> check whether a subarray with sum k present or not
		2.> count number of subarrays with sum k.
		3.> find max length of subarray with k sum.
	*/



	cout << check_subarray_ksum(v, n, k) << " " << endl; //present ->1, not present ->0
	//true -> 1, false -> 0

	cout << "count of subarrays with ksum -> " << count_subarrays_ksum(v, n, k) << " " << endl;

	cout << "max length of subarray with k sum -> " << maxlength_subarray_ksum(v, n, k) << " " << endl;


	return 0;
}