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, 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
hide comments
|
mahabir10:
2018-03-27 23:12:09
what should be the answer for the testcase
|
|
aniket000:
2018-01-11 19:24:05
To those using binary-search and getting WA on test case 10 , make sure to check for the following:
|
|
rinem13:
2017-12-28 07:17:34
AC in one go! 50th |
|
themast3r:
2017-12-21 19:23:46
Can also be solved in O(N ^ 2) using Hashing. Although O(N ^ 2 * log(N)) also gets accepted. |
|
kmkhan_014:
2017-12-19 20:31:45
solution using lower_bound and upper_bounds works fine!!! Last edit: 2017-12-19 20:32:20 |
|
Divyam Shah:
2017-12-11 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:
2017-10-06 12:29:16
Reduced complexity from O(N^2 LogN) to O(N^2) got AC; |
|
vengatesh15:
2017-09-05 08:56:15
use equal_range. AC after 5 TLE |
|
dunjen_master:
2017-08-25 00:25:04
whats feynman algo...can someone provide a link where i can know abt it? |
|
soham_12345:
2017-07-18 20:25:13
O(n^2) complexity.. |
| Added by: | Abhilash I |
| Date: | 2007-02-06 |
| 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 |
RSS