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 2^{28} ) 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
hide comments
ankit_btech:
20180609 20:25:29
@vengatesh15 Yeah me too!!


ayushgupta1997:
20180606 19:22:53
Should do with both HashMap and Vectors to analysise complexity 

rohitnarayan:
20180331 13:26:01
@mahabir10 answer to your question should be 8! 

mahabir10:
20180327 23:12:09
what should be the answer for the testcase


aniket000:
20180111 19:24:05
To those using binarysearch and getting WA on test case 10 , make sure to check for the following:


rinem13:
20171228 07:17:34
AC in one go! 50th 

themast3r:
20171221 19:23:46
Can also be solved in O(N ^ 2) using Hashing. Although O(N ^ 2 * log(N)) also gets accepted. 

kmkhan_014:
20171219 20:31:45
solution using lower_bound and upper_bounds works fine!!! Last edit: 20171219 20:32:20 

Divyam Shah:
20171211 07:07:19
For those getting WA in test case 10  When doing binary search,count the number of times the search key occurs in the array rather than counting it as 1. 

shikhars387:
20171006 12:29:16
Reduced complexity from O(N^2 LogN) to O(N^2) got AC; 
Added by:  Abhilash I 
Date:  20070206 
Time limit:  1.419s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  South western 0506 