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


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 should be printed on a single line.


-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

hide comments
d_sm: 2020-03-09 07:36:55

accepted in one submission , make lhs and rhs two array and then sort ,and search for each lhs the upper and lower bound in rhs.....

fardin_abir: 2020-02-27 19:30:05

holding the meet in the middle concept, first tried with unordered map but got TLE, then tried with two pointers and got AC

bhavikag: 2020-01-31 12:39:10

Has anybody done this in java?

apurv_19: 2019-12-26 12:52:53

ABCDEF...a similar problem to this one...
upper_bound lower_bound didn't work in this as it did in ABCDEF....passed it using equal_range....

iamfahim: 2019-11-03 19:50:54

Using STL equal_range

nadstratosfer: 2019-07-24 04:56:34

Sadly, some datasets have nearly no zero-summing quadruplets, rendering a large assortment of possible optimizations useless. Most people commenting here seem to confuse optimization with not doing stupid stuff, and noone claiming to have done it in O(n^2) has runtime to prove it. I'm still bothered to find the efficient approach candide hinted to, but other than that the problem seems like a waste of time after getting the green bar.

yashranjan74: 2019-06-21 11:18:25

Just use equal range in place of unordered_map. Although the complexity was better using unordered_map but equal_range get AC whereas unordered_map gave TLE.

harry_shit: 2019-06-04 12:10:34

tle for O(n*n) also,using unordered map
edit:equal_range gave ac despite being O(n*n*logn)

Last edit: 2019-06-04 12:39:04
hetp111: 2019-06-01 09:02:24

How did 1st ranker got it in 0.01sec? mine took 2+sec with O(n*n*log(n))...

Last edit: 2019-06-01 09:04:09
abhinav_jain02: 2019-05-18 08:28:58

Note that equal elements in a list are considered to be distinct

Added by:Abhilash I
Time limit:1.419s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:South western 05-06