Algorithm
Problem link- https://www.spoj.com/problems/CRAN02/
CRAN02 - Roommate Agreement
Leonard was always sickened by how Sheldon considered himself better than him. To decide once and for all who is better among them they decided to ask each other a puzzle. Sheldon pointed out that according to Roommate Agreement Sheldon will ask first. Leonard seeing an opportunity decided that the winner will get to rewrite the Roommate Agreement.
Sheldon thought for a moment then agreed to the terms thinking that Leonard will never be able to answer right. For Leonard, Sheldon thought of a puzzle which is as follows. He gave Leonard n numbers, which can be both positive and negative. Leonard had to find the number of continuous sequence of numbers such that their sum is zero.
For example if the sequence is- 5, 2, -2, 5, -5, 9
There are 3 such sequences
2, -2
5, -5
2, -2, 5, -5
Since this is a golden opportunity for Leonard to rewrite the Roommate Agreement and get rid of Sheldon's ridiculous clauses, he can't afford to lose. So he turns to you for help. Don't let him down.
Input
First line contains T - number of test cases
Second line contains n - the number of elements in a particular test case.
Next line contain n elements, ai (1 <= i <= n) separated by spaces.
Output
The number of such sequences whose sum if zero.
Constraints
1 <= t <= 5
1 <= n <= 10^6
-10 <= ai <= 10
Example
Input: 2 4 0 1 -1 0 6 5 2 -2 5 -5 9 Output: 6 3
Code Examples
#1 Code Example with Python Programming
Code -
Python Programming
T = int(input())
for _ in range(T):
N = int(input())
d = dict()
d[0] = 1
sum, result = 0, 0
for i in map(int, input().split()):
sum += i
if d.get(sum) is not None:
result += d[sum]
if d.get(sum) is None:
d[sum] = 1
else:
d[sum] += 1
print(result)Input
4
0 1 -1 0
6
5 2 -2 5 -5 9
Output
3
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
#define MOD (ll)1000000007
#define pb push_back
#define EPS 1e-9
#define FOR(i,n) for(int i = 0;i < n; i++)
#define FORE(i,a,b) for(int i = a;i <= b; i++)
#define pi(a) printf("%d\n", a)
#define all(c) c.begin(), c.end()
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define gc getchar_unlocked
#define sdi(a, b) si(a);si(b)
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl '\n'
#define F first
#define S second
#define FILL(arr, val) memset(arr, val, sizeof(arr))
#define read(arr, n) for(int i = 0;i < n; i++)cin>>arr[i];
#define sp ' '
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
void si(int &x){
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
int main(){
io;
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int arr[n];
read(arr, n);
int pre[n];
FOR(i,n) pre[i] = 0;
unordered_map<int,int> M;
ll ans = 0;
pre[0] = arr[0];
M[0] = 1;
if(arr[0] == 0){
ans++;
M[0]++;
}else{
M[pre[0]] = 1;
}
for(int i = 1;i < n; i++){
pre[i] = pre[i-1] + arr[i];
if(M.find(pre[i]) != M.end()){
ans += M[pre[i]];
int count = M[pre[i]];
M[pre[i]] = count+1;
}else{
M[pre[i]] = 1;
}
}
cout << ans << endl;
}
return 0;
}Input
4
0 1 -1 0
6
5 2 -2 5 -5 9
Output
3
Demonstration
SPOJ Solution-Roommate Agreement-Solution in C, C++, Java, Python