Algorithm
Problem link- https://www.spoj.com/problems/SUMFOUR/
SUMFOUR - 4 values whose sum is 0
The SUM problem can be formulated as follows: given four lists A, B, C, D of integer values, compute how many quadruplet (a, b, c, d ) belongs to A x B x C x D are such that a + b + c + d = 0 . In the following, we assume that all lists have the same size n.
Input
The first line of the input file contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as 228 ) that belong respectively to A, B, C and D.
(Edited: n <= 2500)
Output
Output should be printed on a single line.
Example
Input: 6 -45 22 42 -16 -41 -27 56 30 -36 53 -37 77 -36 30 -75 -46 26 -38 -10 62 -32 -54 -6 45 Output: 5
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <map>
#include <list>
using namespace std;
int a[4001],b[4001],c[4001],d[4001];
int A[16000002];
int B[16000002];
int main(){
int n;
long long sum=0;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d%d%d",&a[i],&b[i],&c[i],&d[i]);
}
long t1=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
A[t1++]=a[i]+b[j];
}
}
t1=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
B[t1++]=-c[i]-d[j];
}
}
sort(A,A+t1);
sort(B,B+t1);
for(long i=0;i<t1;){
long size1=0;
int no=A[i];
while(A[i]==no<t1){
size1++;
i++;
}
long low=0;
long high=t1;
long mid;
long temp=0;
long size=0;
while(low<=high){
mid=(low+high)/2;
if(B[mid]==no){
temp=mid-1;
while(mid<t1&&B[mid]==no){
size++;
mid++;
}
while(temp>=0&&B[temp]==no){
size++;
temp--;
}
break;
}
else if(B[mid]<no){
low=mid+1;
}
else if(B[mid]>no){
high=mid-1;
}
}
sum+=size1*size;
}
printf("%lld\n",sum);
return 0;
}Input
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45
Output
#2 Code Example with Java Programming
Code -
Java Programming
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int const N = 2501;
int n, a[N], b[N], c[N], d[N];
vector<int> all;
int main() {
scanf("%d", &n);
for(int i = 0; i < n; ++i)
scanf("%d %d %d %d", a + i, b + i, c + i, d + i);
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
all.push_back(a[i] + b[j]);
sort(all.begin(), all.end());
pair<vector<int>::iterator, vector<int>::iterator> bounds;
int res = 0;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j) {
int tmp = -(c[i] + d[j]);
bounds = equal_range(all.begin(), all.end(), tmp);
res += bounds.second - bounds.first;
}
printf("%d\n", res);
return 0;
}Input
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45
Output
Demonstration
SPOJ Solution-SUMFOUR 4 values whose sum is 0-Solution in C, C++, Java, Python ,SPOJ Solution,SUMFOUR